继续战dp。不提。

题意分析

这题说白了就是一条01背包问题，因为对于给定的秒数你只要-1s（emmmmm）然后就能当01背包做了——那1s送给劲歌金曲（？）。比较好玩的是这里面dp状态的保存——因为要满足两个条件，因此我们的状态的定义也随之改变，使用自定义的结构体来保存。这个是我以前从来没接触过也没想到的。非常高级了，记下来。感谢想到的dalao！

代码

#include <set>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <cstring>

#include <cstdlib>

#include <iomanip>

#include <iostream>

#include <algorithm>

#define ZERO(x) memset((x),0,sizeof(x))

using namespace std;

int songs[55];

int n,maxt;

struct Node

{

    int cnt,time;

    Node(int _c=0,int _t=0):cnt(_c),time(_t) {}

    bool operator < (const Node& rhs) const

    {

        if(cnt==rhs.cnt) return time<rhs.time;

        else return cnt<rhs.cnt;

    }

} dp[10005];

int main()

{

    int t; cin>>t;

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

    {

        memset(dp,0,sizeof(dp));

        cin>>n>>maxt; maxt--;

        for(int i=1;i<=n;++i)

            cin>>songs[i];

        for(int i=1;i<=n;++i)

            for(int j=maxt;j>=songs[i];--j)

            {

                Node tmp(dp[j-songs[i]].cnt+1,dp[j-songs[i]].time+songs[i]);

                if(dp[j]<tmp) dp[j]=tmp;

            }

        cout<<"Case "<<kase<<": "<<dp[maxt].cnt+1<<" "<<dp[maxt].time+678<<endl;

    }

    return 0;

}

巴特西

【紫书】（UVa12563）Jin Ge Jin Qu hao

题意分析

代码

最新文章

热门文章