mronesong 2012-08-29 04:09:00
点我顶贴
收藏
删除
用二维背包能够做出最小时间,但是怎么保证“泡到最多的MM”这个条件呢?
希望有大神解惑啊?Orz!!!!
另外附上我ac的代码。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxt = 100000;
int rmb[110] , rp[110] , Time[1010];
int dp[110][110];
int n , m , r;
int main() {
scanf("%d",&n);
int tmp = 0;
for(int i=1;i<=n;i++) {
scanf("%d%d%d",rmb + i , rp + i , Time + i);
Time[i] = maxt - Time[i];
}
scanf("%d%d",&m,&r);
for(int i=1;i<=n;i++)
for(int j=m;j>=rmb[i];j--)
for(int k=r;k>=rp[i];k--) {
if(dp[j-rmb[i]][k-rp[i]] + Time[i]> dp[j][k])
dp[j][k] = dp[j-rmb[i]][k-rp[i]] + Time[i];
if(dp[j][k] > tmp) tmp = dp[j][k];
}
printf("%d\n",maxt - tmp % maxt);
//system("pause");
return 0;
}