我理解一下第二篇的一个数组的解法,感觉1e4比2e4更适合(MAXM*MAXR=1e4),推出来也是一个式子,所以就用1e4,但是WA on #7,这是为啥?
代码:
#include<iostream>
using namespace std;
const int N = 110;
int n,m,r,dp[N][N];
struct MM
{
int rmb,rp,time;
}a[N];
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i].rmb >> a[i].rp >> a[i].time;
cin >> m >> r;
for(int i = 1;i <= n;i++)
for(int j = m;j >= a[i].rmb;j--)
for(int k = r;k >= a[i].rp;k--)
dp[j][k] = max(dp[j][k],dp[j - a[i].rmb][k - a[i].rp] + (20000 - a[i].time));
cout << ((dp[m][r] / 20000) + 1) * 20000 - dp[m][r];
return 0;
}