【題解】Green Judge b030: 隨選視訊

0 Shares
0
0
0

題目連結:http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b030

解法:背包問題

#include <iostream>
#include <cstring>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m; //n=總影片數,m=小綠可以觀賞的影片總長度
    int w[n+1], v[n+1];
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i]; //第i部影片有w[i]分鐘,滿足度為v[i]

    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));

    for(int i=1; i<=n; i++){ //考慮看第i部影片的時候
        for(int j=1; j<=m; j++){ //最多只能看j分鐘
            if(j - w[i] < 0){ //長度不夠看第i部影片,故只能不看
                dp[i][j] = dp[i-1][j]; //不看的話,等於只看了i-1部且仍可看j分鐘
            }else{ //長度足夠,可以看或不看(選最大價值)
                dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]); //如果看的話,答案等於看了i-1部,再加上這一部的價值,且剩下j-w[i]分鐘
            }
        }
    }
    cout << dp[n][m] << '\n';
}

分享文章
0 Shares
1 comment
  1. 自動引用通知: live roulette wheel online
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

You May Also Like

Set (集合)

Set 是一個儲存資料的容器,例如陣…