原题链接：http://soj.sysu.edu.cn/1221
题意解读：黑板上写出了一行数字a1,a2,….an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦去的数字之和就是你所得到的分数。 求所得分数最大值。
思路分析：这是一道关于0-1背包的题。类似的题目sicily上还有采药、开心的金明等题，但这道数字游戏稍稍复杂一点。（1）关于背包的容量。m个回合，每用掉一个回合容量就减少1，所以其实背包的容量就是m，每次擦掉数字的代价就是1。（2）关于状态转移方程。弄清楚了（1）之后，其实状态转移方程也就比较好写出来：MAX[i][j]=max(MAX[i-1][j-1]+nums[i].a-(j-1)*nums[i].b,MAX[i-1][j])。（3）关于为什么数据需要排序？这是这道题与普通0-1背包题目的不同之处，主要在于“每擦除一个数，剩下来的每个数字ai都要递减一个值bi”，因为数字的价值在变！所以当然要让bi值大的放在前面，不然在考虑每个数字要不要加进背包时，不能发挥数字的最大价值！！
代码如下：
#include <iostream> #include <memory.h> #include <algorithm> using namespace std; struct num{ int a,b; }; bool cmp(num x,num y){ return x.b>y.b; } int max(int a,int b){ if(a>b) return a; else return b; } int main(){ int n,m; cin>>n>>m; int MAX[n+1][m+1]; num nums[n+1]; for(int i=1;i<=n;i++) cin>>nums[i].a; for(int i=1;i<=n;i++) cin>>nums[i].b; sort(nums+1,nums+n+1,cmp); memset(MAX,0,sizeof(MAX)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) MAX[i][j]=max(MAX[i-1][j-1]+nums[i].a-(j-1)*nums[i].b,MAX[i-1][j]); cout<<MAX[n][m]<<endl; return 0; }