洛谷 [P1280] 尼克的任務

DP

題目問的是最大空暇時間，那麼就定義dp[i]為第i分鐘的最大空暇時間，顯然滿足最優子結構，我們發現dp[i]僅與其後的值有關，那麼從後往前推，如果第i分鐘沒有任務，dp[i]=dp[i+1],如果有任務，就周遊所有任務 dp[i]=max{dp[i+task[j]]}

即本問題可以看成分組背包問題

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
int read(){
    int rv=,fh=;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<)+(rv<<)+c-'0';
        c=getchar();
    }
    return rv*fh;
}
vector <int> t[];
int n,k,dp[];
int main(){
    freopen("in.txt","r",stdin);
    n=read();k=read();
    for(int i=;i<=k;i++){
        int a=read(),b=read();
        t[a].push_back(b);
    }
    /*for(int i=1;i<=n;i++){
        dp[i]=0x7fffffff/3;
    }*/
    for(int i=n;i>=;i--){
        if(t[i].size()){
            for(int j=;j<t[i].size();j++){
                dp[i]=max(dp[i],dp[i+t[i][j]]);
            }
        }else dp[i]=dp[i+]+;
    }
    cout<<dp[];
    fclose(stdin);
    return ;
}