竞赛讨论区 > 用类似0-1背包的做法怎么不行

用类似0-1背包的做法怎么不行

头像
大鱼🐠201810081101291
编辑于 2019-06-24 15:58:42 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览384
分别用m[50],p[50],r[50]来存储题的分数、每分钟减少的分数、花费的时间;就可以开始打表了;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=T;j++)
{
if(j>=r[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-r[i]]+(m[i]-j*r[i]));
else
dp[i][j]=dp[i-1][j];
}
}
这样怎么不行,dp[i][j]的意思是有i个题在j时间里的最大分数;
下面是我都完整代码
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int dp[50][1000000];
int main()
{
int N,T;
cin>>N>>T;
int m[50],p[50],r[50];//题的分数、每分钟减少的分数、花费的时间
for(int i=1;i<=N;i++)
cin>>m[i];
for(int i=1;i<=N;i++)
cin>>p[i];
for(int i=1;i<=N;i++)
cin>>r[i];
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++)
{
for(int j=1;j<=T;j++)
{
if(j>=r[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-r[i]]+(m[i]-j*r[i]));
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[N][T]<<endl;
return 0;
}

1条回帖

回帖
加载中...
回帖

本文相关内容

等你来战

查看全部

热门推荐