题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4237
这题可以转化为每次可以走g~d+x步，求最大分数，且最大分数的步数最少。
这题的数据范围比较小，可以用奇怪的姿势过。
首先，lyf队长给的方法是n^3的dp过；用我自己的方法是搜索也可以过，因为数据小。
但是，如果数据范围很大，就得用复杂度是O(n)的单调队列dp来做。
上次做过一道单调队列的dp问题，当时比较懵懂，现在，对这个方法有了更深的理解。而且，只要把id丢进单调队列里即可（因为可以通过id查找dp的值）。具体过程还是看代码仔细理解吧：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <queue> 4 #include <set> 5 using namespace std; 6 typedef pair<int,int> pii; 7 8 const int inf =0x3f3f3f3f; 9 int n,x,g,d; 10 int a[100+5]; 11 pii dp[100+5]; 12 13 pii solve() 14 { 15 deque<int> Q; 16 dp[0]=pii(0,0); 17 for(int i=1;i<=n;i++) 18 { 19 while(!Q.empty() && Q.front()<i-d) Q.pop_front(); 20 if(i-g>=0 && dp[i-g].first != -inf) 21 { 22 while(!Q.empty() && dp[Q.back()] <= dp[i-g]) Q.pop_back(); 23 Q.push_back(i-g); 24 } 25 if(!Q.empty()) dp[i] = pii(dp[Q.front()].first + a[i],dp[Q.front()].second - 1); 26 //因为题目要求最大分数的最小步数，而对pair的max是默认取大的值， 27 //所以取个反就是最大化（-步数） 28 else dp[i] = pii(-inf,0); 29 } 30 pii ret = pii(-inf,0); 31 for(int i=0;i<=n;i++) 32 { 33 if(i>=n-d+1) ret=max(ret,dp[i]); 34 //如果处于再跳一步就可以出去的状态的话 35 } 36 ret.second = -ret.second + 1; 37 //加1是细节，因为还需要一步跳出 38 return ret; 39 } 40 41 int main() 42 { 43 int T; 44 scanf("%d",&T); 45 while(T--) 46 { 47 scanf("%d%d%d%d",&n,&x,&g,&d); 48 d += x; 49 for(int i=1;i<=n;i++) scanf("%d",a+i); 50 pii ans = solve(); 51 printf("%d %d ",ans.first,ans.second); 52 } 53 return 0; 54 }
同时，因为pair的比较方法，这里必须把步数转换成负数的。如果不这样就必须写比较器：
1 bool operator < (const std::pair<int,int> &a,const std::pair<int,int> &b) { 2 if (a.first != b.first) return a.first < b.first; 3 return a.second > b.second; 4 } 5 6 bool operator <= (const std::pair<int,int> &a,const std::pair<int,int> &b) { 7 return a == b || a < b; 8 }
也可以用写cmp的方式，像sort一样传入第三个参数cmp，同时把dp[Q.back()] <= dp[i-g]改成(max(dp[Q.back()],dp[i-g],cmp) == dp[i-g]) 就行，但是不如上面那样写比较器来的逻辑清晰。
同时，这题有个奇怪的地方在于，重载了以后max还是会出错，必须 if (ret < dp[i]) ret = dp[i];来代替max才行。但是，自己试验了别的代码以后发现，重载了以后max函数是可以生效的，这里真是有毒啊。还是”留坑以后填“吧。。