UVa 12563 Jin Ge Jin Qu hao 0-1背包问题

UVa 12563 Jin Ge Jin Qu hao 0-1背包问题

The question is from here

My Solution：

刘老师给了我们那么多的数据是为了告诉我们: 歌曲的总时间不会超过 n*180-1+678 及 50*180-1+678 = 9677

并不像题中的t <= 10^9那么吓人，最多 9677了，所以可以dp[ n ] [ t ];求最大歌曲数，且在此前提下时间尽可能长

//Your goal is simple: sing as many songs as possible, and leave KTV as late as possible (since we have rule 3, this also //maximizes the total lengths of all songs we sing) when there are ties.

题目中的这句话当时没有理解对，多花了好多时间，因为如果 d , dw 分开 dp 则可能时间最多的时候歌曲数不是最多，这样就WA了

而事实上是leave KTV as late as possible when there are ties.  要使用if语句 搞一起 

算法 ：0-1背包问题的方法 用 规划方向，边读入边计算 

#include 
#include 
#include 
//#define LOCAL
using namespace std;

int d[52][40000],dw[52][40000];

int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int T,n,t,w,ans, kase = 1;
    scanf("%d", &T);
    while(T--){
        ans = 0;
        scanf("%d%d", &n, &t);
        for(int i = 1; i <= n; i++){ scanf("%d", &w); for(int j = t; j > 0; j--){
                d[i][j] = (i == 1 ? 0 : d[i-1][j]);
        /*      像这样分开 dp 在这里是错的
                if(j > w) d[i][j] = max(d[i][j], d[i-1][j-w]+1);

                dw[i][j] = (i == 1 ? 0 : dw[i-1][j]);
                if(j > w ) dw[i][j] = max(dw[i][j], dw[i-1][j-w]+w);
        */
                dw[i][j] = (i == 1 ? 0 : dw[i-1][j]);
                if(j > w){
                    int& a = d[i][j];
                    int& b = d[i-1][j-w];
                    if(a < b+1) {a = b+1; dw[i][j]=dw[i-1][j-w]+w;}
                    else if(a == b+1) dw[i][j] = max(dw[i][j],dw[i-1][j-w]+w);

                }
            }
        }
        //求 max{d[n][i]}即为最大歌曲数
        for(int i = 1; i <= t; i++){ if(d[n][i] > ans) ans = d[n][i];// time = i;}
        }
        //cout<<dw[n][t]<<endl;
        printf("Case %d: ",kase++);
        printf("%d %dn",ans+1,dw[n][t]+678);

    }
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx