UVA 12563 Jin Ge jin Qu [h] ao 劲歌金曲 (01背包)


每首只能唱一次,而且中间不能不唱歌,所以先把状态赋值为-1,以区别合法状态和非法状态,在唱歌曲目最多的条件下,离开时间应该尽量晚。

状态定义f[i][j]考虑前i首歌唱歌时间为j的最大唱歌曲目

#include<bits/stdc++.h>
using namespace std;

const int maxn = 55;

const int maxt = 180*maxn+679;

int f[maxt];


const int JinGe = 678;
int main()
{
    //freopen("in.txt","r",stdin);
    int T; scanf("%d",&T);
    int kas = 0;
    while(T--){
        int n,t; scanf("%d%d",&n,&t);
        int k = 0;
        memset(f,-1,sizeof(int)*t);
        f[0] = 0;
        for(int i = 0; i < n; i++){
            int V ; scanf("%d",&V);
            for(int j = t-1; j >= V; j--){
                if(~f[j-V] && ( f[j] < f[j-V]+1 ) ){
                    f[j] = f[j-V]+1;
                    if(f[j] > f[k] || ( f[j] == f[k] && k < j )  ){
                        k = j;
                    }
                }
            }
        }

        printf("Case %d: %d %d\n",++kas,f[k]+1,k+JinGe);

    }
    return 0;
}

优质内容筛选与推荐>>
1、window下phpstudy的nginx配置虚拟主机
2、asp.net 从Web.config 传递参数到后台
3、Java笔记
4、java web 之 BeanUtils.populate的作用
5、silverlight 2.0 参数传递


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号