讨论 / 如何保证前提“泡到最多的MM”?
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;

}

#1 330459659@2012-08-29 04:09:00
回复 删除
额 我是开的两个数组维护的。。。 一个是维护最多美眉个数,一个是同步维护花费的最少时间。
#2 lzt2002@2015-07-08 06:33:56
回复 删除
zan

hehe

查看更多回复
提交回复