uva12563

첫 번째 문제라고 할 수 있죠DP, 이렇게 말하는 것도 아니고, 첫 번째 문제를 이해하는 거예요. 아직 알 듯 모를 듯하지만.
그러나 한 가지 방법은 초기화하고 상태의 전환은 점차적으로 값을 부여한 다음에 새로운 상태와 비교하는 것이다.오케이.
제목의 뜻은 먼저 노래의 수가 가장 많다는 것을 명확히 보증한 다음에 수조를 만들어 노래를 부르는 시간이 가장 길다는 것을 기록해야 한다.OK
UVA 12563

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;

//            ，        ，              
//        
int path[55][10005];
int dp[55][10005];      // i   j          ；
int n,t;
int val[55];

void debug()
{
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dp[i][t-1]);
    }
    printf("
");
}

int main()
{
    int T;
    int qq=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&t);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
        }
        memset(path,0,sizeof(path));
        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=t-1;j++)
            {
                dp[i][j]=dp[i-1][j];
                path[i][j]=path[i-1][j];
                if(j>=val[i])
                {
                    if(dp[i][j]<dp[i-1][j-val[i]]+1)
                    {
                        dp[i][j]=dp[i-1][j-val[i]]+1;
                        path[i][j]=path[i-1][j-val[i]]+val[i];
                    }
                    else if(dp[i][j]==dp[i-1][j-val[i]]+1)
                    {
                        path[i][j]=max(path[i][j],path[i-1][j-val[i]]+val[i]);
                    }
                }
            }
        }
        int max_=-1;

        for(int i=1;i<=n;i++)
        {
            if(max_<dp[n][t-1])
            {
                max_=dp[n][t-1];
            }
        }
       // debug();

        printf("Case %d: %d %d
",qq++,max_+1,path[n][t-1]+678);
    }
    return 0;
}



/* 3 100 60 70 80 3 100 30 69 70 3 12 11 1 1 */