UVALive 4870 Roller Coaster --01背包

题意:过山车有n个区域,一个人有两个值F,D,在每个区域有两种选择:

1.睁眼: F += f[i], D += d[i]

2.闭眼: F = F ,     D -= K

问在D小于等于一定限度的时候最大的F。

解法: 用DP来做,如果定义dp[i][j]为前 i 个,D值为j的情况下最大的F的话,由于D值可能会增加到很大,所以是存不下的,又因为F每次最多增加20,那么1000次最多增加20000,所以开dp[1000][20000],dp[i][j]表示前 i 个,F值为j的情况下最小的D。

然后就是简单的01背包了。也可以转化为一维背包。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std; int dp[][];
int F[],D[]; int main()
{
int n,K,Limit,i,j,FV;
while(scanf("%d%d%d",&n,&K,&Limit)!=EOF && n+K+Limit)
{
FV = ;
for(i=;i<=n;i++) { cin>>F[i]>>D[i]; FV += F[i]; }
for(i=;i<=n;i++) {
for(j=;j<=FV;j++)
dp[i][j] = Mod;
}
dp[][] = ;
for(i=;i<=n;i++) {
for(j=;j<=FV;j++) {
dp[i][j] = min(dp[i][j],max(,dp[i-][j]-K));
if(j >= F[i] && dp[i-][j-F[i]]+D[i] <= Limit)
dp[i][j] = min(dp[i][j],dp[i-][j-F[i]]+D[i]);
}
}
int maxi = ;
for(i=;i<=FV;i++) {
if(dp[n][i] <= Limit)
maxi = max(maxi,i);
}
cout<<maxi<<endl;
}
return ;
}
上一篇:CentOS7 yum lamp 虚拟主机配置 lamp各组件简单影响性能的参数调整--for 一定的环境需求


下一篇:多动手试试,其实List类型的变量在页面上取到的值可以直接赋值给一个js的Array数组变量