/ Vijos / 讨论 / 采药 /

AC

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

int dp[1005] ;
int happy[105] ;
int cost[105] ;

int main()
{
int n , time;
cin>>time ;cin>>n ;

memset(dp,0,sizeof(dp));
memset(happy,0,sizeof(happy)) ;
memset(cost,0,sizeof(cost)) ;

for(int i = 0 ; i < n ; i++)
{
cin>>cost[i]>>happy[i] ;
}
for(int i =0 ; i < n ; i++)
for(int j = time ; j >= cost[i] ; j -- ){
if( dp[j] < dp[j-cost[i]]+happy[i] )
dp[j] = dp[j-cost[i]]+happy[i] ;
// if(dp[j]<dp[j-cost[i]]+happy[i])
// dp[j] = dp[j-cost[i]]+happy[i] ;
}
cout <<dp[time]<< endl;
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1104
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
16859
已通过
6541
通过率
39%
被复制
41
上传者