讨论 / 动态规划,类似于机器分配问题
沧海一声喵 2018-03-01 03:01:16
点我顶贴 收藏 删除
#include <cstdio>

using namespace std;

int main(){

int i,j,k,T,n,name,a[11][201]={0},dp[11][101]={0};

scanf("%d%d%d",&T,&n,&name);

for(i=1;i<=n;i++)

for(j=name+1;j<=name+T;j++) scanf("%d",&a[i][j]);

for(i=1;i<=n;i++)

for(j=1;j<=T;j++)

for(k=0;k<=j;k++)

if(dp[i-1][k]+a[i][j-k]>dp[i][j]) dp[i][j]=dp[i-1][k]+a[i][j-k];

printf("%d",dp[n][T]);

return 0;}

//dp[i][j]:前i科在j时间内可得到的最高分

dp[i][j]=max{dp[i-1][j-k]+a[i][k]|k=0,...,j}

其中a[i][k]表示第i科花费k时间的得分

查看更多回复
提交回复