题目描述：
输入格式：
输入文件的第一行是一个整数
n
（
1
<
=
n
<
=
2000
）
n（1<=n<=2000）
n（1<=n<=2000），表示数字个数；第二行一个整数
m
（
1
<
=
m
<
=
n
）
m（1<=m<=n）
m（1<=m<=n），表示回合数，接下来一行有n个不超过
10000
10000
10000的正整数，
a
1
，
a
2
，
a
3
，
?
，
a
n
a1，a2，a3，\cdots，an
a1，a2，a3，?，an表示原始序列，最后一行有n个不超过
500
500
500的正整数，
b
1
，
b
2
，
b
3
，
?
，
b
n
b1，b2，b3，\cdots，bn
b1，b2，b3，?，bn，表示每回合每个数字递减的值。
输入样例：
3
3
10 20 30
4 5 6
输出样例：
47
解题思路：
首先我们要有一个损失数值的概念。
我们先来思考一下，倘若 a i a_i ai? 比 a j a_j aj? 先取走，并且 b i < b j b_i<b_j bi?<bj?，那么很显然，经过一轮后 a j a_j aj? 的值会下降 b j b_j bj?，损失的数值为 b j b_j bj?；若先取走 a j a_j aj? 再取走 a i a_i ai?，损失数值为 b i b_i bi?，因为 b i < b j b_i<b_j bi?<bj?，所以答案更优。
也就是说， b b b 值越大的数越先取走，我们的损失数值总和会降得越小，答案会更优。因此，我们先将 b b b 数组由大到小排序，然后在从左到右取 m m m 个数，即为最优取数方式。
由于 m ≠ n m\ne n m?=n，因此我们并非所有数都要取，因此需要一个动态规划的策略找到最优解。
设
f
i
,
j
f_{i,j}
fi,j? 表示在前
i
i
i 个数中取
j
j
j 个数（即第
j
j
j 个回合）所能取到的最大数值。
若不取第
i
i
i 个数字，那么这个状态等价于在前
i
?
1
i-1
i?1 个数中取
j
j
j 个数的最大值。
若取第
i
i
i 个数字，那么这个状态等价于在前
i
?
1
i-1
i?1 个数中取
j
?
1
j-1
j?1 个数的最大值，再加上 第
i
i
i 个数第
j
j
j 个回合时的数值。
f
i
,
j
=
max
?
{
f
i
?
1
,
j
不
选
第
i
个
数
f
i
?
1
,
j
?
1
+
a
i
?
b
i
?
(
j
?
1
)
选
第
i
个
数
f_{i,j}=\max\begin{cases} f_{i-1,j}&不选第 i 个数\\ f_{i-1,j-1}+a_i-b_i*(j-1)&选第 i 个数\\ \end{cases}
fi,j?=max{fi?1,j?fi?1,j?1?+ai??bi??(j?1)?不选第i个数选第i个数?
然后就是重中之重！本人就是在这里栽倒了好多次。状态的初值必须要赋好，否则很容易DP错误！
这题中的初始状态有这些：
- f i , 0 = 0 ???????????????????????? i = 1 ? n f_{i,0}=0~~~~~~~~~~~~~~~~~~~~~~~~i=1\cdots n fi,0?=0????????????????????????i=1?n
- f i , 1 = max ? ( a i ) ???????????? i = 1 ? n f_{i,1}=\max(a_i)~~~~~~~~~~~~i=1\cdots n fi,1?=max(ai?)????????????i=1?n
- o t h e r s ? 为 ? ∞ others~为-\infty others?为?∞
这个状态在空间上还可以优化： f i , j f_{i,j} fi,j? 只能从 f i ? 1 , j f_{i-1,j} fi?1,j? 推出来，因此我们可以把第一维省略掉。
CODE：
空间优化前：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct QWQ
{
int a,b;
} e[2010];
bool cmp(QWQ a,QWQ b)
{
return a.b>b.b;
}
int f[2001][2001]={0};
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>e[i].a;
for(int i=1;i<=n;i++) cin>>e[i].b;
sort(e+1,e+1+n,cmp);
memset(f,-0x7f,sizeof(f));
f[0][0]=0;
f[1][1]=e[1].a;
for(int i=2;i<=n;i++)
f[i][1]=max(f[i-1][1],e[i].a);
for(int i=1;i<=n;i++)
{
for(int j=2;j<=min(i,m);j++) //由于j=1的情况上面已经作为初始状态做了，就不能再做一次了，所以从2开始
{
f[i][j]=max(f[i-1][j],f[i-1][j-1]+e[i].a-e[i].b*(j-1));
}
}
cout<<f[n][m];
return 0;
}
空间优化后：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct QWQ
{
int a,b;
} e[2010];
bool cmp(QWQ a,QWQ b)
{
return a.b>b.b;
}
int f[2001]={0};
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>e[i].a;
for(int i=1;i<=n;i++) cin>>e[i].b;
sort(e+1,e+1+n,cmp);
memset(f,-0x7f,sizeof(f));
for(int i=1;i<=n;i++)
{
f[0]=0; //任何个数字的第 0 回合都不会取到分数
for(int j=m;j>=1;j--) //这里为了保证f[j-1]为上一回合的，01背包的倒叙循环同理。
{
f[j]=max(f[j],f[j-1]+e[i].a-e[i].b*(j-1));
}
f[1]=max(f[1],e[i].a); //任何个数字取一个都是选最大
}
cout<<f[m];
return 0;
}