遊樂園問題

int main(){
    int n,t;
    while(cin>>n>>t){
        vector<int> a(n);
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a.begin(),a.end());

        vector<vector<int>> dp(n,vector<int>(t));
        for(int i=0;i<t;i++)
            dp[0][i]=0;
        for(int i=0;i<n;i++)
            dp[i][0]=0;
        for(int i=1;i<n;i++)
            for(int j=1;j<t;j++){
                if(j<a[i])
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1]]+a[i-1]);
            }
        cout<<dp[n-1][t-1]+a[n-1]<<endl;
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/lqwh/p/7566007.html