問題描述
小藍要去健身，他可以在接下來的?1～n 天中選擇一些日子去健身。
他有?m?個健身計劃，對于第?i?個健身計劃，需要連續的??天，如果成功完成，可以獲得健身增益?si??，如果中斷，得不到任何增益。
同一個健身計劃可以多次完成，也能多次獲得健身增益，但是同一天不能同時進行兩個或兩個以上的健身計劃。
但是他的日程表中有?q?天有其他安排，不能去健身，問如何安排健身計劃，可以使得?n?天的健身增益和最大。
輸入格式
第一行輸入三個整數?n,m,q 。
第二行輸入?q?個整數，t1,t2,t3...tq??，代表有其他安排的日期。
接下來?m?行，每行輸入兩個整數?ki,si??。代表該訓練計劃需要? 天，完成后可以獲得?si??的健身增益。
輸出格式
一個整數，代表最大的健身增益和。
樣例輸入
10 3 3
1 4 9
0 3
1 7
2 20
樣例輸出
30
說明
在樣例中?2～3 天進行計劃?2?，5～8 天進行計劃?3?，?10～10?天進行計劃?1?。
評測數據范圍
數據范圍：?1≤q≤n≤2×?，?1≤m≤50 ，?1≤si≤
?，?0≤ki≤20 ，?1≤t1<t2<...<tq≤n 。
?
?
完全背包問題，枚舉空閑段天數，每一段使用完全背包
問題轉化
每個健身計劃?
i?是一個“物品”：
體積：
v[i]（需要的天數）。價值：
w[i]（健身增益）。背包容量：
day[k]（當前區間的可用天數）。目標：在不超過?
day[k]?的情況下，選擇若干健身計劃（可重復），使總價值最大。狀態轉移
f[j] = max(f[j], f[j - v[i]] + w[i])：
f[j]：不選當前計劃。
f[j - v[i]] + w[i]：選當前計劃，剩余天數?j - v[i]?的最優解加上當前價值。
#include<iostream>
#include<cmath>
#include<algorithm>#define int long long
using namespace std;const int N = 2e5+10;
int n, m, q;
int k[N];
int t[N]; //存儲由其他安排的日期
int v[N], w[N];
int day[N]; //day[i]：第i個區間的可用天數
int dp[N]; //dp[i]：表示用 i 天能獲得的最大增益
int ans;signed main()
{cin>>n>>m>>q;for(int i=1; i<=q; ++i) cin>>t[i];for(int i=1; i<=m; ++i) cin>>k[i]>>w[i];//計算每個區間的可用天數t[0]=1, t[q+1]=n; //為了計算day[i]賦的值 for(int i=q+1; i>0; --i){if(i==1 || i==q+1) day[i] = t[i] - t[i-1];else day[i] = t[i] - t[i-1]-1;} //計算每個健身計劃需要的連續天數 for(int i=1; i<=m; ++i){v[i]= pow(2, k[i]);}for(int i=1; i<=q+1; ++i) //遍歷每個可健身區間{for(int j=1; j<=m; ++j) //遍歷每個健身計劃{for(int p=v[j]; p<=day[i]; ++p){dp[p] = max(dp[p], dp[p-v[j]] + w[j]);}}ans += dp[day[i]];}cout<<ans;return 0;
}
