Agony


私信TA

用户名:dzc21

访问量:41692

签 名:

CSDN博客:http://blog.csdn.net/qq_38712932

等  级
排  名 42
经  验 7743
参赛次数 0
文章发表 81
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

CSDN博客:http://blog.csdn.net/qq_38712932 个人博客:http://www.eternallyc.top/blog/index

解题思路:

 

逐渐求最大值
(模板题,-多阶段决策问题)

注意事项:

遍历是从最大值数组中的1到你拥有的时间t



参考代码:

#include <cstdio>

#include <algorithm>

using namespace std;

int a[10005];

int w[10005];

int f[1000005];

int main()

{

    int t,m;

    scanf("%d %d",&t,&m);

    for(int b = 1; b <= m; b ++)

        scanf("%d %d",&a[b],&w[b]);

    for(int b = 1; b <= m; b ++)

        for(int c = t; c >= a[b]; c--)

            f[c]=max(f[c],f[c-a[b]]+w[b]);

    f[0] = 0;

    for(int b = 1; b<=t; b ++)

        f[0]=max(f[0],f[b]);

    printf("%d",f[0]);


    return 0;

}


 

0.0分

0 人评分

  评论区