欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA - 12563

程序员文章站 2022-06-01 22:52:53
...

这题是求两个状态的分先后级别的最优解的0/1背包变形。

参考博客:

https://www.cnblogs.com/shi2015/p/4661971.html

https://blog.csdn.net/u013480600/article/details/40376143

说几个细节点:

(1)

UVA - 12563

0/1背包里面没有这个判断条件,是因为要满足:

UVA - 12563

这个要求。如果j==T[i]的时候,会有dp[0]==0,所以就不能进入这个条件里面,所以要特意判断一下。

因为如果不是这种情况,dp[i]==0即代表时间i内不能刚刚好唱完dp[i]首歌。

 

(2)

UVA - 12563

1处一定要判断maxn 是否为0,因为如果maxn是0那么在表示刚刚好唱完i首歌的dp[i]也满足条件了,就会不满足

UVA - 12563

这个条件。(maxn=0表示 在给定时间内无法唱完任何一首歌)

 

2处一定要是最小的一首歌的时间,而不能是1,因为会崩。所以要多一步排序。

 

(3)

UVA - 12563

这里数组不能开太大(竟然返回tle。。。无语)虽然题目中说的t<=1e9,但是这里1e7也可以过,可能是数据太弱????

 

代码:

//G
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 60
#define MAXN2 10000000

int T[MAXN];
int dp[MAXN2];

int main()
{
    int i,j;
    int kase,casenum;
    int n;
    int t;
    int ans;
    int maxn;

    scanf("%d",&casenum);
    kase=0;
    while(casenum--)
    {
        scanf("%d%d",&n,&t);
        memset(T,0,sizeof(T));
        for(i=1;i<=n;i++)
            scanf("%d",&T[i]);
        memset(dp,0,sizeof(dp));
        maxn=0;
        for(i=1;i<=n;i++)
        {
            for(j=t-1;j>=T[i];j--)
            {
                if(dp[j-T[i]]>0||j==T[i])
                {
                    dp[j]=max(dp[j],dp[j-T[i]]+1);
                    maxn=max(maxn,dp[j]);
                }
            }
        }
        ans=0;
        sort(T+1,T+1+n);
        if(maxn)
        {
            for(i=t-1;i>=T[1];i--)
            {
                if(dp[i]==maxn)
                {
                    ans=maxn;
                    break;
                }
            }
        }
        else
            ans=i=0;
        ans++;
        i+=678;
        printf("Case %d: %d %d\n",++kase,ans,i);
    }
    return 0;
}