【题解】洛谷P1311 [NOIP2011TG] 选择客栈（递推）

题目来源：洛谷P1311

思路

纯暴力明显过不了这道题

所以我们要考虑如何优化到至多只能到nlogn

但是我们发现可以更优到O(n)

我们假设我们当前寻找的是第二个人住的客栈i

那么第一个人住的客栈肯定在i之前

如果在枚举的时候发现一家客栈满足小于可承受价格

那么这家客栈左边与i客栈颜色相同的都可以视为一种方案

所以我们需要一个数组sum[k]记录到i之前第k种颜色一共有几家客栈

last[k]数组存下第k种颜色在i之前的最后一家客栈（判断满足价格的客栈颜色是否在此这种颜色最后一家位置的后面）

num[k]数组存下第k种颜色到i之前一共有几种可行方案

枚举时每次记录下满足价格的客栈i

观察其位置是否满足大于跟它同色的客栈

如果满足的话num数组更新为sum的值

每次枚举都要更新ans加上当前客栈颜色可行的方案（因为前面的可行的话对此客栈同意可行）sum数组 last数组

代码

#include<iostream> using namespace std; #define maxn 55 int n,m,p,ans,col,cost,temp; int sum[maxn],num[maxn],last[maxn]; int main() { cin>>n>>m>>p; for(int i=1;i<=n;i++) { cin>>col>>cost; if(cost<=p) temp=i;//记录满足价格的位置 if(temp>=last[col]) num[col]=sum[col];//如果大于同色的最后一个客栈位置即可更新 ans+=num[col]; last[col]=i; sum[col]++; } cout<<ans; }

 

转载于:https://www.cnblogs.com/BrokenString/p/9862119.html