P2786题解

DayC · 2018-01-13 22:20:27 · 题解

此题为一道二维费用背包题。(若是不规定“必须按照创作的时间顺序在所有的CD盘上出现”，就是一道排序水题)

与裸的二维费用不同，此题不同点在于状态转移方程。

此题的状态转移方程为：

*F[m][t]=max{
    f[m][t]//不选当前歌曲
    f[m-1][T]+1//用一张新的CD来存当前歌曲（m张CD不够存的情况）
    f[m][t-time[i]]+1//一张CD放多首歌曲
}*

F[m][t]表示用m张CD，最后一张CD用t分钟所能存的最大歌曲数 time[i]表示第i首哥的时间

    #include<iostream>
    #include<cstring>
    #include<iostream>
    #define maxn 21
    using namespace std;
    int N,T,M;
    int f[maxn][maxn];//用于保存状态
    int t[maxn];
    int max(int i,int j,int k){
        i=max(i,j);
        i=max(i,k);
        return i;
    }
    int main(){
        cin>>N>>T>>M;
        for(int i=1;i<=N;i++){
            cin>>t[i];
        }
        for(int i=0;i<=T;i++){//初始化数组
            f[0][i]=0;
        }
        for(int i=1;i<=N;i++){
            for(int m=M;m>=1;m--){//注意：因为是01背包，所以要从后往前更新状态
                for(int j=T;j>=t[i];j--){
                    f[m][j]=max(f[m][j],f[m-1][T]+1,f[m][j-t[i]]+1);//状态转移
                }
            }
        }
        cout<<f[M][T];
    }