0x50「動(dòng)態(tài)規(guī)劃」例題
幾點(diǎn)總結(jié)
1 DP三要素：狀態(tài)绒净，階段，決策偿衰。具體地講挂疆，若DP時(shí)是雙重循環(huán)，第一重循環(huán)通常表示狀態(tài)和階段下翎，第二重循環(huán)表示決策缤言。若DP時(shí)是三重循環(huán)，第一重循環(huán)通常表示階段视事，第二重循環(huán)和第一重循環(huán)共同組成狀態(tài)胆萧，第三重循環(huán)表示決策。三者必須按照由外而內(nèi)依次循環(huán)俐东。
2 DP三條件：子問(wèn)題重疊跌穗，最優(yōu)子結(jié)構(gòu)性質(zhì)，無(wú)后效性虏辫。對(duì)于前兩點(diǎn)蚌吸，和遞歸的條件和性質(zhì)類似，決定了DP實(shí)現(xiàn)的兩種寫(xiě)法：迭代和遞歸砌庄。而無(wú)后效性則表示DP已經(jīng)求解過(guò)的子問(wèn)題不受后續(xù)影響羹唠，換言之，DP對(duì)狀態(tài)空間的遍歷是要求狀態(tài)空間是DAG娄昆，DAG中的節(jié)點(diǎn)對(duì)應(yīng)狀態(tài)佩微，邊對(duì)應(yīng)狀態(tài)轉(zhuǎn)移的過(guò)程，轉(zhuǎn)移的選让妊妗（走哪條邊）就是DP中的決策喊衫，遍歷結(jié)果是DAG的一個(gè)拓?fù)湫颉＃≒S：若出現(xiàn)后效性杆怕，通常會(huì)通過(guò)一次強(qiáng)制鏈接和一次強(qiáng)制斷開(kāi)來(lái)解決族购，在某些環(huán)形DP/基環(huán)樹(shù)問(wèn)題里常見(jiàn)）
線性DP
線性DP指具有線性“階段”劃分的動(dòng)態(tài)規(guī)劃算法，若狀態(tài)空間有多個(gè)維度陵珍，每個(gè)維度上都有線性變化的“階段”寝杖，那么它就是線性DP。
經(jīng)典問(wèn)題
LIS
狀態(tài)表示：F[i]表示以A[i]為結(jié)尾的LIS長(zhǎng)度
轉(zhuǎn)移方程：互纯，其中
且
邊界：
目標(biāo)：瑟幕，其中
時(shí)間復(fù)雜度：
LIS變形問(wèn)題
Q：把序列A變成單調(diào)不下降的序列，至少需要修改幾個(gè)數(shù)留潦？
A：序列A的總長(zhǎng)度-A的最長(zhǎng)不下降子序列長(zhǎng)度
e.g. A={3,2,1,4,2}只盹，A的最長(zhǎng)不下降子序列{3,4}，只要把A改成{3,3,3,4,4}即可（共修改5-2=3個(gè)數(shù)）
Q：把序列A變成嚴(yán)格單調(diào)遞增的序列兔院，至少需要修改幾個(gè)數(shù)殖卑？
A：因?yàn)楸ＷC嚴(yán)格單調(diào)遞增，所以不能用上面的構(gòu)造方法坊萝。設(shè)B[i]=A[i]-i孵稽，答案就是序列A的總長(zhǎng)度-B的最長(zhǎng)不下降子序列長(zhǎng)度
e.g. A={2,2,4,3,4}，則B={1,0,1,0,-1}十偶，B的最長(zhǎng)不下降子序列{0,1}菩鲜，只要把B改成{-INF,0,1,INF,INF}即可，此時(shí)A={-INF+1,1,3,INF+4,INF+5}（共修改5-2=3個(gè)數(shù)）若模仿上面一題的計(jì)算方法惦积，用A序列的總長(zhǎng)度-A序列的LIS長(zhǎng)度接校，得到答案為5-3=2錯(cuò)誤，原因在于無(wú)法通過(guò)只改變A序列中的第三個(gè)元素4做到左右平衡狮崩。
LCS
狀態(tài)表示：F[i,j]表示以A[1...i]和B[1...j]的LCS長(zhǎng)度
轉(zhuǎn)移方程：
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
數(shù)字三角形
狀態(tài)表示：F[i][j]表示從左上角走到第i行第j列的最大和
轉(zhuǎn)移方程：
邊界：
目標(biāo)：蛛勉，其中
時(shí)間復(fù)雜度：
例題
POJ2279 Mr Young's Picture Permutations
我們將所有人按照從高到低的順序放入整個(gè)序列中，這樣就有了DP的順序厉亏。
狀態(tài)表示：F[a1,a2,a3,a4,a5]表示各排從左端起分別站了a1,a2,a3,a4,a5人的方案數(shù)量
轉(zhuǎn)移方程：
3~5排同理
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=30+1;
const int maxk=5+5;
const int INF=0x3f3f3f3f;
ll f[maxn][maxn][maxn][maxn][maxn],k,num[maxk];
int main() {
ios::sync_with_stdio(false);
// freopen("Mr Young's Picture Permutations.in","r",stdin);
while(cin>>k&&k) {
memset(num,0,sizeof(num));
//memset(f,0,sizeof(f));
f[0][0][0][0][0]=1;
for(int i=1; i<=k; i++) {
cin>>num[i];
}
for(ll a1=1; a1<=num[1]; a1++) {
for(ll a2=0; a2<=min(num[2],a1); a2++) {
for(ll a3=0; a3<=min(num[3],a2); a3++) {
for(ll a4=0; a4<=min(num[4],a3); a4++) {
for(ll a5=0; a5<=min(num[5],a4); a5++) {
ll &p=f[a1][a2][a3][a4][a5];
p=0;
if(a1-1>=a2) p+=f[a1-1][a2][a3][a4][a5];
if(a2-1>=a3) p+=f[a1][a2-1][a3][a4][a5];
if(a3-1>=a4) p+=f[a1][a2][a3-1][a4][a5];
if(a4-1>=a5) p+=f[a1][a2][a3][a4-1][a5];
if(a5-1>=0) p+=f[a1][a2][a3][a4][a5-1];
}
}
}
}
}
cout<<f[num[1]][num[2]][num[3]][num[4]][num[5]]<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5101 LCIS
狀態(tài)表示：F[i,j]表示以A[1...i]和B[1...j]構(gòu)成的以B[j]結(jié)尾的LCIS長(zhǎng)度
轉(zhuǎn)移方程：
即
邊界：
目標(biāo)：
樸素實(shí)現(xiàn)這個(gè)轉(zhuǎn)移方程爱只，復(fù)雜度為皿淋。
但是我們自己觀察這個(gè)方程，會(huì)發(fā)現(xiàn)當(dāng)?shù)诙友h(huán)變量j時(shí)恬试，我們可以將第一層循環(huán)變量i視為定值窝趣，這讓B[k]<A[i]這個(gè)條件是固定的。這意味著當(dāng)j+1時(shí)训柴，k的取值范圍從[0,j)變成了[0,j+1)哑舒，也就是說(shuō)层亿，這時(shí)決策集合的下界不變吮螺，上界最多增加一個(gè)可能的最優(yōu)決策尼夺，那么我們只要O()判斷這個(gè)B[j]<A[i]是否滿足即可確定新的j能否有可能產(chǎn)生最優(yōu)決策桩警。
具體實(shí)現(xiàn)上，我們?cè)诿看芜M(jìn)入第一層循環(huán)時(shí)膘滨，維護(hù)一個(gè)變量val表示決策集合中F[i-1,k]的最大值甘凭，在每次j的范圍增大時(shí)，判斷j能否進(jìn)入決策集合即可火邓。這樣的操作避免了重復(fù)掃描丹弱，時(shí)間復(fù)雜度O()，代碼如下铲咨，其中method_1為樸素算法躲胳，method_2為優(yōu)化算法。
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3000+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][maxn],a[maxn],b[maxn],ans=0;
int main() {
ios::sync_with_stdio(false);
//freopen("LCIS.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]==b[j]){
for(int k=0;k<j;k++){
if(b[k]<a[i]){
f[i][j]=max(f[i-1][k]+1,f[i][j]);
}
}
}
else f[i][j]=f[i-1][j];
if(i==n) ans=max(ans,f[n][j]);
}
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3000+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][maxn],a[maxn],b[maxn],ans=0;
int main() {
ios::sync_with_stdio(false);
// freopen("LCIS.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
int val=0;
if(b[0]<a[i]) val=max(val,f[i-1][0]);
for(int j=1;j<=n;j++){
if(a[i]==b[j]){
f[i][j]=val+1;
}
else f[i][j]=f[i-1][j];
if(b[j]<a[i]) val=max(val,f[i-1][j]);
if(i==n) ans=max(ans,f[n][j]);
}
}
cout<<ans;
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
5102 Mobile Service
狀態(tài)表示：F[i,x,y,z]表示完成了前i個(gè)請(qǐng)求纤勒，三個(gè)服務(wù)員分別在x,y,z位置的最小花費(fèi)
轉(zhuǎn)移方程：
題目要求同一位置不能有多個(gè)員工坯苹，所以要用if語(yǔ)句判斷轉(zhuǎn)移合法性
邊界：
目標(biāo)：
按照這個(gè)方程，時(shí)間復(fù)雜度
但是仔細(xì)觀察會(huì)發(fā)現(xiàn)踊东，當(dāng)完成前i個(gè)請(qǐng)求時(shí)北滥，必然有一個(gè)員工位于位置，因此只需要知道i和兩名員工的位置闸翅，就可以推出第三個(gè)員工的位置再芋，即消去了冗余狀態(tài)
故更改定義如下
狀態(tài)表示：F[i,x,y]表示完成了前i個(gè)請(qǐng)求，兩個(gè)服務(wù)員分別在x,y位置的最小花費(fèi)（第三個(gè)員工在位置）
轉(zhuǎn)移方程：
題目要求同一位置不能有多個(gè)員工坚冀，所以要用if語(yǔ)句判斷轉(zhuǎn)移合法性
邊界：
目標(biāo)：
按照這個(gè)方程济赎，時(shí)間復(fù)雜度：，代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int maxl=200+5;
const int INF=0x3f3f3f3f;
int l,n,f[maxn][maxl][maxl],c[maxl][maxn],p[maxn];
int main() {
ios::sync_with_stdio(false);
// freopen("Mobile Service.in","r",stdin);
cin>>l>>n;
for(int i=1; i<=l; i++) {
for(int j=1; j<=l; j++) {
cin>>c[i][j];
}
}
for(int i=1; i<=n; i++) cin>>p[i];
memset(f,INF,sizeof(f));
f[0][1][2]=0;
p[0]=3;
int ans=INF;
for(int i=1; i<=n; i++) {
for(int x=1; x<=l; x++) {
for(int y=1; y<=l; y++) {
if(x==y) continue;
if(f[i-1][x][y]==INF) continue;
int z=p[i-1];
if(x!=p[i]&&y!=p[i])f[i][x][y]=min(f[i-1][x][y]+c[z][p[i]],f[i][x][y]);
if(z!=p[i]&&y!=p[i])f[i][z][y]=min(f[i-1][x][y]+c[x][p[i]],f[i][z][y]);
if(x!=p[i]&&z!=p[i])f[i][x][z]=min(f[i-1][x][y]+c[y][p[i]],f[i][x][z]);
// if(i==n) ans=min(ans,f[n][x][y]);
//不能在這里更新 因?yàn)閒[n][x][y]可能尚未達(dá)到最優(yōu)解记某，因?yàn)楹竺鎯蓚€(gè)維度不一定保證遞增
}
}
}
for(int x=1; x<=l; x++)
for(int y=1; y<=l; y++)
ans=min(ans,f[n][x][y]);
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ3666 Making the Grade
引理：記答案為S司训，則在滿足S最小的前提下，一定存在一種構(gòu)造B序列的方案液南，使得B中的數(shù)值都在A中出現(xiàn)過(guò)壳猜。
狀態(tài)表示：F[i]表示已經(jīng)構(gòu)造好前i個(gè)數(shù)，以B[i]為結(jié)尾的序列的最小S值滑凉，即此時(shí)B[i]=A[i]
轉(zhuǎn)移方程：统扳，其中
且
cost(j+1,i-1)表示構(gòu)造B[j+1]...B[i-1]滿足A[j]B[j+1]
...
B[i-1]
A[i]時(shí)，
的最小值
方程解釋：DP方程中的i就是最新的一段數(shù)中與A相同的位置畅姊，j是上一段數(shù)中這樣的位置咒钟，因此cost(j+1,i-1)就是把區(qū)間中前一部分變成A[j]后一部分變成A[i]的最小代價(jià)。
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：若未，其中計(jì)算cost的時(shí)間復(fù)雜度：
考慮優(yōu)化cost的計(jì)算過(guò)程朱嘴，我們做如下的狀態(tài)定義
狀態(tài)表示：F[i,j]表示已經(jīng)構(gòu)造好前i個(gè)數(shù)，以B[i]=j為結(jié)尾的序列的最小S值粗合，即此時(shí)B[i]=A[i]=j
轉(zhuǎn)移方程：萍嬉，其中
邊界：乌昔，其中
目標(biāo)：，其中
時(shí)間復(fù)雜度：
空間復(fù)雜度：
考慮優(yōu)化時(shí)間和空間復(fù)雜度
1 離散化A序列
時(shí)間復(fù)雜度：
空間復(fù)雜度：
2 類比之前LCIS的轉(zhuǎn)移方程帚湘，這里變量k的變化玫荣，即決策集合的變化仍滿足隨著j的增大只增不減的性質(zhì)，所以做出同樣的優(yōu)化大诸。
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下，其中method_1僅僅進(jìn)行了離散化贯卦，結(jié)果為T(mén)LE资柔。method_2進(jìn)行了上述兩種優(yōu)化，結(jié)果為AC撵割。
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],b[maxn],f[maxn][maxn],cnt;
int main() {
ios::sync_with_stdio(false);
freopen("Making the Grade.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n+1);
cnt=unique(b+1,b+n+1)-b-1;
/*
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
}
*/
int ans=INF;
memset(f,INF,sizeof(f));
for(int i=1;i<=cnt;i++) f[0][i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
for(int k=1;k<=j;k++){
f[i][j]=min(f[i-1][k]+abs(a[i]-b[j]),f[i][j]);
}
if(i==n) ans=min(ans,f[n][j]);
}
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],b[maxn],f[maxn][maxn],cnt;
int main() {
ios::sync_with_stdio(false);
// freopen("Making the Grade.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n+1);
cnt=unique(b+1,b+n+1)-b-1;
/*
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
}
*/
int ans=INF;
memset(f,INF,sizeof(f));
for(int i=0;i<=cnt;i++) f[0][i]=0;
for(int i=1;i<=n;i++){
int val=f[i-1][0];
for(int j=1;j<=cnt;j++){
val=min(val,f[i-1][j]);
f[i][j]=val+abs(a[i]-b[j]);
if(i==n) ans=min(ans,f[n][j]);
}
}
cout<<ans;
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
5103 傳紙條
從左上角走到右下角一個(gè)來(lái)回 等價(jià)于 兩個(gè)人同時(shí)從左上角出發(fā)走到右下角
狀態(tài)表示：F[x1,y1,x2,y2]表示第一個(gè)人在(x1,y1)第二個(gè)人在(x2,y2)的最大收益
此時(shí)時(shí)間復(fù)雜度：
考慮優(yōu)化
觀察后發(fā)現(xiàn)贿堰，設(shè)目前路徑長(zhǎng)度為i，則x1+y1=x2+y2=i+2（因?yàn)閮扇送瑫r(shí)行走）
所以通過(guò)i,x1,x2就可以確定y1,y2
修改狀態(tài)表示如下
狀態(tài)表示：F[i,x1,x2]表示第一個(gè)人在x1行啡彬，第二個(gè)人在x2行羹与，目前路徑長(zhǎng)度為i的最大收益（此時(shí)y1=i+2-x1,y2=i+2-x2）
轉(zhuǎn)移方程：每個(gè)人有兩種移動(dòng)方式，兩個(gè)人移動(dòng)狀態(tài)共有四種庶灿，這里以兩人均向右為例：
即兩人從(x1,y1)(x2,y2)走向(x1,y1+1)(x2,y2+1)
若x1=x2且y1+1=y2+1纵搁，說(shuō)明兩人路徑在此處相交，答案累加一次：
否則分別累加答案：
邊界：F[0,1,1]=A[1,1]
目標(biāo)：F[n+m-2,n,n]
時(shí)間復(fù)雜度：O()
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int INF=0x3f3f3f3f;
int a[maxn][maxn],f[maxn*2][maxn][maxn],n,m;
int main() {
ios::sync_with_stdio(false);
// freopen("傳紙條.in","r",stdin);
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
}
}
f[0][1][1]=a[1][1];
for(int i=1; i<=n+m-2; i++) {
for(int j=1; j<=min(n,i+1); j++) {
for(int k=1; k<=min(n,i+1); k++) {
int Y1=i+2-j;
int Y2=i+2-k;
if((Y1>=1&&Y1<=m)&&(Y2>=1&&Y2<=m)) {
if(j==k&&Y1==Y2) {
f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a[j][Y1]);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+a[j][Y1]);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+a[j][Y1]);
f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+a[j][Y1]);
} else {
f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a[j][Y1]+a[k][Y2]);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+a[j][Y1]+a[k][Y2]);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+a[j][Y1]+a[k][Y2]);
f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+a[j][Y1]+a[k][Y2]);
}
}
}
}
}
cout<<f[n+m-2][n][n];
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5104 I-country
考慮凸連通塊性質(zhì)：任何一個(gè)凸連通塊可以劃分成若干行往踢，每行的左端點(diǎn)列號(hào)先減小后增大腾誉，右端點(diǎn)列號(hào)先增大后減小。
狀態(tài)表示：F[i,j,l,r,x,y]表示前i行峻呕，選了j個(gè)格子利职，其中第i行選了第l到r的格子，左輪廓的單調(diào)性是x,右輪廓的單調(diào)性是y（0表示遞增瘦癌，1表示遞減）時(shí)猪贪，能構(gòu)成的凸連通塊的最大權(quán)值和
轉(zhuǎn)移方程：其中A為每行的前綴和數(shù)組，即
1.左邊界列號(hào)遞減讯私，右邊界列號(hào)遞增（兩邊界都處于擴(kuò)張狀態(tài)）
2.左右邊界列號(hào)都遞減（左邊界擴(kuò)張热押，右邊界收縮）
3.左右邊界列號(hào)都遞減（左邊界收縮，右邊界擴(kuò)張）
4.左邊界列號(hào)遞增妄帘，右邊界列號(hào)遞減（兩邊界都處于收縮狀態(tài)）
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
本題還需要輸出方案楞黄，對(duì)于DP問(wèn)題輸出方案，通常是使用一個(gè)/多個(gè)與F數(shù)組同樣大小的數(shù)組來(lái)記錄每一次轉(zhuǎn)移的最優(yōu)解的取值抡驼，然后在DP結(jié)束后鬼廓，從終態(tài)向初態(tài)遞歸，依次在回溯時(shí)輸出答案致盟。
代碼如下碎税，其中method_1沒(méi)有輸出方案尤慰，method_2輸出方案
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int maxk=225+5;
const int INF=0x3f3f3f3f;
int n,m,k,a[maxn][maxn],s[maxn][maxn],f[maxn][maxk][maxn][maxn][2][2];
/*
f[i][j][l][r][x][y] 表示前i行 占據(jù)了j個(gè)格子 第i行從l列到r列 左端點(diǎn)狀態(tài)為x 右端點(diǎn)狀態(tài)為y 的最大權(quán)值
x=0 表示列號(hào)遞增 x=1 表示列號(hào)遞減
*/
int main() {
ios::sync_with_stdio(false);
freopen("I-country.in","r",stdin);
cin>>n>>m>>k;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
s[i][j]=s[i][j-1]+a[i][j];
}
}
// cout<<s[2][3]<<endl;
for(int i=1; i<=n; i++) {
for(int j=0; j<=k; j++) {
for(int l=1; l<=m; l++) {
for(int r=l; r<=m; r++) {
if(j-(r-l+1)<0) break;
for(int p=l; p<=r; p++) {
for(int q=p; q<=r; q++) {
f[i][j][l][r][1][0]=max(f[i][j][l][r][1][0],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
}
}
for(int p=l; p<=r; p++) {
for(int q=r; q<=m; q++) {
f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1]);
}
}
for(int p=1; p<=l; p++) {
for(int q=l; q<=r; q++) {
f[i][j][l][r][0][0]=max(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
f[i][j][l][r][0][0]=max(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1]);
}
}
for(int p=1; p<=l; p++) {
for(int q=r; q<=m; q++) {
f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][0][1]+s[i][r]-s[i][l-1]);
f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1]);
f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1]);
}
}
}
}
}
}
int ans=-INF;
for(int i=1; i<=n; i++) {
for(int l=1; l<=m; l++) {
for(int r=l; r<=m; r++) {
for(int x=0; x<=1; x++) {
for(int y=0; y<=1; y++) {
ans=max(ans,f[i][k][l][r][x][y]);
}
}
}
}
}
cout<<"Oil : "<<ans<<endl;
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int maxk=225+5;
const int INF=0x3f3f3f3f;
int n,m,k,a[maxn][maxn],s[maxn][maxn],f[maxn][maxk][maxn][maxn][2][2];
/*
f[i][j][l][r][x][y] 表示前i行 占據(jù)了j個(gè)格子 第i行從l列到r列 左端點(diǎn)狀態(tài)為x 右端點(diǎn)狀態(tài)為y 的最大權(quán)值
x=0 表示列號(hào)遞增 x=1 表示列號(hào)遞減
*/
struct method{
int l,r,x,y;
}met[maxn][maxk][maxn][maxn][2][2];
int ai,aj,al,ar,ax,ay;
void update(int now,int l,int r,int x,int y){
int &ans=f[ai][aj][al][ar][ax][ay];
method &p=met[ai][aj][al][ar][ax][ay];
if(ans>=now) return;
ans=now;
p.l=l;
p.r=r;
p.x=x;
p.y=y;
}
void print(int i,int j,int l,int r,int x,int y){
if(j==0) return;
method &p=met[i][j][l][r][x][y];
print(i-1,j-(r-l+1),p.l,p.r,p.x,p.y);
for(int ii=l;ii<=r;ii++){
cout<<i<<" "<<ii<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("I-country.in","r",stdin);
cin>>n>>m>>k;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
s[i][j]=s[i][j-1]+a[i][j];
}
}
// cout<<s[2][3]<<endl;
for(int i=1; i<=n; i++) {
for(int j=0; j<=k; j++) {
for(int l=1; l<=m; l++) {
for(int r=l; r<=m; r++) {
if(j-(r-l+1)<0) break;
ai=i;
aj=j;
al=l;
ar=r;
ax=1;
ay=0;
for(int p=l; p<=r; p++) {
for(int q=p; q<=r; q++) {
update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
}
}
ax=1;
ay=1;
for(int p=l; p<=r; p++) {
for(int q=r; q<=m; q++) {
update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
update(f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1],p,q,1,1);
}
}
ax=0;
ay=0;
for(int p=1; p<=l; p++) {
for(int q=l; q<=r; q++) {
update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
update(f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1],p,q,0,0);
}
}
ax=0;
ay=1;
for(int p=1; p<=l; p++) {
for(int q=r; q<=m; q++) {
update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
update(f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1],p,q,1,1);
update(f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1],p,q,0,0);
update(f[i-1][j-(r-l+1)][p][q][0][1]+s[i][r]-s[i][l-1],p,q,0,1);
}
}
}
}
}
}
int ans=-INF;
for(int i=1; i<=n; i++) {
for(int l=1; l<=m; l++) {
for(int r=l; r<=m; r++) {
for(int x=0; x<=1; x++) {
for(int y=0; y<=1; y++) {
if(f[i][k][l][r][x][y]>ans){
ans=f[i][k][l][r][x][y];
ai=i;
al=l;
ar=r;
ax=x;
ay=y;
}
}
}
}
}
}
cout<<"Oil : "<<ans<<endl;
print(ai,k,al,ar,ax,ay);
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
5105 Cookies
引理：貪婪度大的孩子餅干多。
證明：將所有孩子按照貪婪度降序排序雷蹂，獲得的餅干數(shù)單調(diào)遞減伟端。若交換兩個(gè)相鄰的孩子g[i]和g[i+1]（鄰項(xiàng)交換，滿足g[i]>g[i+1]）匪煌，則原來(lái)兩個(gè)孩子產(chǎn)生的怨氣是g[i]×(i-1)+g[i+1]×i责蝠，交換后產(chǎn)生的怨氣是g[i+1]×(i-1)+g[i]×i，即會(huì)對(duì)答案產(chǎn)生g[i]-g[i+1]的貢獻(xiàn)萎庭，而其他孩子的怨氣不變霜医，所以經(jīng)過(guò)反證法，交換后的結(jié)果顯然不優(yōu)于原單調(diào)序列驳规。
根據(jù)引理肴敛，我們將所有孩子的貪婪度遞減排序，從左向右DP吗购。
至此医男，我們已經(jīng)通過(guò)額外的算法確定了DP順序，現(xiàn)在考慮如何表示狀態(tài)捻勉。
狀態(tài)表示：F[i,j]表示給前i個(gè)孩子分配j塊餅干的最小怨氣和
我們做出如下轉(zhuǎn)化
1 若第i個(gè)孩子餅干數(shù)為1镀梭，則枚舉i前面有多少孩子的餅干數(shù)也為1（這些孩子不會(huì)對(duì)第i個(gè)孩子產(chǎn)生貢獻(xiàn)）
2 若第i個(gè)孩子的餅干數(shù)大于1，則等價(jià)于分配j-i塊餅干給前i個(gè)孩子贯底，每人少拿一塊餅干丰辣，餅干相對(duì)數(shù)量不變，故答案不變禽捆。
狀態(tài)表示：F[i]表示以A[i]為結(jié)尾的LIS長(zhǎng)度
轉(zhuǎn)移方程：
PS：解釋下轉(zhuǎn)化1的轉(zhuǎn)移方程笙什，枚舉k表示[k+1,i]的孩子也是一塊餅干，那么[k+1,i]的孩子總共獲得了i-k塊餅干胚想，剩余餅干數(shù)就是j-(i-k)琐凭。與此同時(shí)，前k個(gè)孩子獲得的餅干數(shù)大于一塊浊服，所以后面的[k+1,i]個(gè)孩子會(huì)因此產(chǎn)生怨氣统屈，怨氣值為
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
這題輸出方案的方式和上一題類似，故不再贅述
代碼如下 牙躺，其中method_1沒(méi)有輸出方案愁憔，method_2輸出方案
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=30+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,g[maxn],f[maxn][maxm],s[maxn];
bool cmp(int x,int y){
return x>y;
}
int main() {
ios::sync_with_stdio(false);
freopen("Cookies.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>g[i];
sort(g+1,g+n+1,cmp);
for(int i=1;i<=n;i++) s[i]=s[i-1]+g[i];
memset(f,INF,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=m;j++){
f[i][j]=min(f[i][j],f[i][j-i]);
for(int k=0;k<i;k++){
f[i][j]=min(f[i][j],f[k][j-(i-k)]+k*(s[i]-s[k]));
}
}
}
cout<<f[n][m];
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=30+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,g[maxn],f[maxn][maxm],s[maxn],c[maxn],a[maxn][maxm],b[maxn][maxm],ans[maxn];
bool cmp(int x,int y){
return g[x]>g[y];
}
void print(int n,int m){
if(n==0) return;
print(a[n][m],b[n][m]);
if(a[n][m]==n){
for(int i=1;i<=n;i++) ans[c[i]]++;
}
else{
for(int i=a[n][m]+1;i<=n;i++) ans[c[i]]=1;
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("Cookies.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>g[i],c[i]=i;
sort(c+1,c+n+1,cmp);
for(int i=1;i<=n;i++) s[i]=s[i-1]+g[c[i]];
memset(f,INF,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=m;j++){
f[i][j]=f[i][j-i];
a[i][j]=i;
b[i][j]=j-i;
for(int k=0;k<i;k++){
if(f[i][j]>f[k][j-(i-k)]+k*(s[i]-s[k])){
f[i][j]=f[k][j-(i-k)]+k*(s[i]-s[k]);
a[i][j]=k;
b[i][j]=j-(i-k);
}
}
}
}
cout<<f[n][m]<<endl;
print(n,m);
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
背包DP
背包問(wèn)題是線性DP中的一類特殊模型。
經(jīng)典問(wèn)題
01背包
狀態(tài)表示：F[i,j]表示從前i個(gè)物品中選出總體積為j的物品放入背包
轉(zhuǎn)移方程：
邊界：
目標(biāo)：孽拷，其中
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下
memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++)
f[i][j] = f[i - 1][j];
for (int j = v[i]; j <= m; j++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
考慮優(yōu)化空間復(fù)雜度
因?yàn)槊恳浑A段的i的狀態(tài)之和i-1的狀態(tài)有關(guān)吨掌，所以可以用滾動(dòng)數(shù)組優(yōu)化
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下
int f[2][MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++)
f[i & 1][j] = f[(i - 1) & 1][j];
for (int j = v[i]; j <= m; j++)
f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; j++)
ans = max(ans, f[n & 1][j]);
考慮繼續(xù)優(yōu)化
實(shí)現(xiàn)轉(zhuǎn)移方程時(shí)，每次都會(huì)進(jìn)行一次從F[i-1][]到F[i][]的拷貝，這提示我們直接省略F數(shù)組的第一維
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下
int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++)
ans = max(ans, f[j]);
對(duì)于為什么j為倒序循環(huán)的解釋：
F數(shù)組的后半部分F[j...m]處于第i個(gè)階段膜宋，也就是已經(jīng)考慮過(guò)放入第i個(gè)物品的情況窿侈。
F數(shù)組的前半部分F[0...j-1]處于第i-1個(gè)階段，也就是尚未考慮過(guò)放入第i個(gè)物品的情況秋茫。
隨著j的不斷減小史简，我們不斷用第i-1個(gè)階段的狀態(tài)F[j - v[i]]來(lái)更新F[j]，就保證了第i個(gè)物品最多可能被放入背包一次肛著。
如果j正序循環(huán)圆兵，可能導(dǎo)致如下情況，F(xiàn)[j]被F[j-v[i]]+w[i]更新策泣，接下來(lái)j增大到j(luò)+v[i]時(shí)衙傀，F(xiàn)[j+v[i]]又被F[j]+w[i]更新，即兩個(gè)同時(shí)處于第i個(gè)階段的狀態(tài)產(chǎn)生了轉(zhuǎn)移萨咕，相當(dāng)于第i個(gè)物品被使用了兩次。
完全背包
狀態(tài)表示：F[i,j]表示從前i個(gè)物品中選出總體積為j的物品放入背包
轉(zhuǎn)移方程：
邊界：
目標(biāo)：火本，其中
時(shí)間復(fù)雜度：
根據(jù)上面對(duì)于01背包循環(huán)的推論危队，只要將原先程序中的j的循環(huán)順序改為正序，就對(duì)應(yīng)了每個(gè)物品可以使用無(wú)限次的情況钙畔。
代碼如下
int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++)
ans = max(ans, f[j]);
多重背包
將每種物品拆成C[i]個(gè)茫陆，類比01背包考慮，狀態(tài)轉(zhuǎn)移方程略擎析。
代碼如下
unsigned int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= c[i]; j++)
for (int k = m; k >= v[i]; k--)
f[k] = max(f[k], f[k - v[i]] + w[i]);
int ans = 0;
for (int i = 0; i <= m; i++)
ans = max(ans, f[i]);
時(shí)間復(fù)雜度：O()
考慮優(yōu)化時(shí)間復(fù)雜度
優(yōu)化方法1 對(duì)于每種物品進(jìn)行二進(jìn)制拆分簿盅，將每種物品拆成O(log)個(gè)。
優(yōu)化方法2 單調(diào)隊(duì)列（詳見(jiàn)單調(diào)隊(duì)列優(yōu)化DP）
分組背包
問(wèn)題描述：n組物品揍魂，第i組里有個(gè)物品桨醋，每個(gè)物品有各自的體積和價(jià)值，現(xiàn)在每組物品中最多選擇一個(gè)物品现斋，在總體積不超過(guò)m的情況下喜最，令價(jià)值和盡量大。
狀態(tài)表示：F[i,j]表示從前i組物品中選出總體積為j的物品放入背包
轉(zhuǎn)移方程：
邊界：
目標(biāo)：庄蹋，其中
時(shí)間復(fù)雜度：
考慮優(yōu)化空間復(fù)雜度
和01背包一樣瞬内，由于每組只選最多一個(gè)物品，所以省略掉F數(shù)組的第一維
注意：
1 需令第二重倒序循環(huán).
2 每一組內(nèi)的c[i]個(gè)物品的循環(huán)k要放在循環(huán)j的內(nèi)層限书，因?yàn)閕是階段虫蝶，i和j共同構(gòu)成狀態(tài)，k是決策倦西，即第i組內(nèi)用哪個(gè)物品能真，三者順序不能錯(cuò)亂。
3 分組背包是很多樹(shù)形DP的基本模型。
代碼如下
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= c[i]; k++)
if (j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
例題
5201 數(shù)字組合
01背包
狀態(tài)表示：F[j]表示當(dāng)外層循環(huán)到第i個(gè)數(shù)時(shí)舟陆，和為j的方案數(shù)
轉(zhuǎn)移方程：
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=10000+5;
const int INF=0x3f3f3f3f;
int f[maxm],n,m,a[maxn];
int main() {
ios::sync_with_stdio(false);
// freopen("數(shù)字組合.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--) f[j]+=f[j-a[i]];
cout<<f[m];
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5202 自然數(shù)拆分Lunatic版
完全背包
狀態(tài)表示：F[j]表示當(dāng)外層循環(huán)到第i個(gè)數(shù)時(shí)误澳，和為j的方案數(shù)
轉(zhuǎn)移方程：
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
空間復(fù)雜度：
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=4000+5;
const ll mod=2147483648;
const int INF=0x3f3f3f3f;
ll f[maxn],n;
int main() {
ios::sync_with_stdio(false);
// freopen("自然數(shù)拆分Lunatic版.in","r",stdin);
f[0]=1;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++) f[j]=(f[j]+f[j-i])%mod;
if(f[n]!=0) cout<<f[n]-1;
else cout<<mod-1;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1015 Jury Compromise
01背包
狀態(tài)表示：F[j,k]表示當(dāng)外層循環(huán)到i時(shí)，選出了j個(gè)人秦躯，辯方總分和控方總分差為k時(shí)忆谓，雙方總分的最大值。
轉(zhuǎn)移方程：
邊界：
目標(biāo)：踱承，滿足|k|盡量小倡缠，|k|相同時(shí)，F(xiàn)[m,k]盡量大
時(shí)間復(fù)雜度：
注意：
1 j一維要倒序循環(huán)茎活，滿足每個(gè)候選人只能選擇一次昙沦。
2 path[i,j,k]表示F[j,k]取得最優(yōu)值時(shí)的候選人方案，輸出方案時(shí)载荔，從F[j,k]不斷向F[j-1,k-(a[D[j,k]]-b[D[j,k]])]遞歸盾饮，一直到達(dá)F[0,0]，遞歸過(guò)程中的所有path[i,j,k]就是答案懒熙。注意雖然背包DP中的F數(shù)組可以省略第一維丘损，但是path數(shù)組為了保存方案，必須要加上第一維工扎。
3 F[j-1,k-(a[i]-b[i])]中k-(a[i]-b[i])可能出現(xiàn)負(fù)數(shù)徘钥，導(dǎo)致數(shù)組下標(biāo)越界，所以需要統(tǒng)一進(jìn)行數(shù)組下標(biāo)平移肢娘，詳見(jiàn)代碼中的zero常量呈础。
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int maxm1=20+5;
const int maxm=900+5;
const int zero=450;
const int INF=0x3f3f3f3f;
int n,m,a[maxn],b[maxn],f[maxm1][maxm],path[maxn][maxm1][maxm],kase=0,suma,sumb,c[maxm1];
void find(int x,int y,int z) {
if(!y) return;
int temp=path[x][y][z+zero];
suma+=a[temp];
sumb+=b[temp];
c[y]=temp;
find(temp-1,y-1,z-(a[temp]-b[temp]));
}
int main() {
ios::sync_with_stdio(false);
// freopen("Jury Compromise.in","r",stdin);
while(cin>>n>>m&&n&&m) {
memset(f,0xcf,sizeof(f));
memset(path,0,sizeof(path));
int mx=m*20;
f[0][zero]=0;
for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
for(int i=1; i<=n; i++) {
for(int j=m; j>=1; j--) {
for(int k=-mx; k<=mx; k++) {
path[i][j][k+zero]=path[i-1][j][k+zero];
if((f[j-1][k+zero-(a[i]-b[i])]>=0) && (k-(a[i]-b[i])>=-mx) && (k-(a[i]-b[i])<=mx)) {
if(f[j-1][k+zero-(a[i]-b[i])]+a[i]+b[i]>f[j][k+zero]) {
f[j][k+zero]=f[j-1][k+zero-(a[i]-b[i])]+a[i]+b[i];
path[i][j][k+zero]=i;
}
}
}
}
}
int ans=mx;
for(int i=0; i<=mx; ++i) {
if(f[m][i+zero]>=0&&f[m][i+zero]>=f[m][-i+zero]) {
ans=i;
break;
}
if(f[m][-i+zero]>=0) {
ans=-i;
break;
}
}
// cout<<ans;
suma=sumb=0;
find(n,m,ans);
sort(c+1,c+m+1);
cout<<"Jury #"<<++kase<<endl;
cout<<"Best jury has value "<<suma<<" for prosecution and value "<<sumb<<" for defence: "<<endl;
for(int i=1; i<=m; i++) cout<<" "<<c[i];
cout<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1742 Coins
多重背包
狀態(tài)表示：F[j]表示當(dāng)外層循環(huán)到i時(shí)，前i種硬幣能否拼成j
轉(zhuǎn)移方程：
邊界：
目標(biāo)：
時(shí)間復(fù)雜度：
樸素算法代碼如下
bool f[100010];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= c[i]; j++)
for (int k = m; k >= a[i]; k--)
f[k] |= f[k - a[i]];
int ans = 0;
for (int i = 1; i <= m; i++)
ans += f[i];
考慮優(yōu)化
優(yōu)化方法1 二進(jìn)制拆分或單調(diào)隊(duì)列
優(yōu)化方法2 注意到這里僅關(guān)注“可行性”橱健，不關(guān)注“最優(yōu)性”而钞，因此仔細(xì)分析DP過(guò)程，可以發(fā)現(xiàn)畴博，若前i種硬幣能夠拼成面值j笨忌，只有兩種可能：
1 前i-1種硬幣能夠拼成面值j，第i重循環(huán)開(kāi)始前俱病，F(xiàn)[j]=1
2 使用了第i種硬幣官疲，因?yàn)镕[j-a[i]]=1，所以推出F[j]=1
于是考慮貪心：設(shè)used[j]表示F[j]在階段i時(shí)為1至少需要用多少枚第i種硬幣亮隙，并且盡量選擇第一種情況途凫。具體地說(shuō)，若F[j-a[i]]=1時(shí)溢吻，F(xiàn)[j]已經(jīng)為1维费，則不進(jìn)行DP果元，否則進(jìn)行轉(zhuǎn)移F[j]|=F[j-a[i]]，同時(shí)令used[j]=used[j-a[i]]+1
時(shí)間復(fù)雜度：
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=100000+5;
const int INF=0x3f3f3f3f;
int n,m,c[maxn],f[maxm],used[maxm],v[maxn],ans;
int main() {
ios::sync_with_stdio(false);
// freopen("Coins.in","r",stdin);
while(cin>>n>>m&&n&&m){
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<=n;i++) cin>>c[i];
memset(f,0,sizeof(f));
ans=0;
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++) used[j]=0;
for(int j=v[i];j<=m;j++){
//貪心策略 //多重背包
if(!f[j]&&f[j-v[i]]&&used[j-v[i]]<c[i]){
f[j]=1;
used[j]=used[j-v[i]]+1;
}
}
}
for(int i=1;i<=m;i++) if(f[i]) ans++;
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
