Codeforce 366 C. Dima and Salad 解析(思維、DP)

今天我們來看看CF366C
題目連結

題目
略。直接看原題即可

前言

覺得可能是用到類似$\sum a_i$這種$dp$狀態，但居然沒想到$\sum a_i-kb_i$這種比較合理的狀態…

想法

令
$dp[已觀察到第幾個食物][\sum a_i-kb_i(也就是差值)]=目前為止，差值為\sum a_i-kb_i的選擇的最大\sum a_i$
由於差值有可能為負，所以需要加個$offset$來儲存
以下寫出$dp$轉移式，假設已經處理好了使得不會超出矩陣範圍:
$dp[i+1][j]=\max{dp[i][j],dp[i][j-(a_{i+1}-kb_{i+1})]+a[i+1]}$
以上是考慮到:「不包含第$i+1$個食物」和「包含第$i+1$個食物且包含前面的食物」
最後要考慮到:「只包含第$i+1$個食物」
注意$dp$陣列一開始要初始化為一個極小值，代表達成這個差值的配置不存在。

程式碼:

const int _n=110;  
int t,n,k,a[_n],b[_n],dp[_n][200010],off=100000;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>k;rep(i,0,n)cin>>a[i];rep(i,0,n)cin>>b[i];  
  rep(i,0,n)rep(j,-100000,100001)dp[i][j+off]=-1e9;  
  dp[0][a[0]-k*b[0]+off]=a[0];  
  rep(i,1,n){  
    rep(j,-100000,100001){  
      int disp=j+off;  
      t=(disp-a[i]+k*b[i]<0 or disp-a[i]+k*b[i]>200000)?-1e9:dp[i-1][disp-a[i]+k*b[i]]+a[i];  
      dp[i][disp]=max(dp[i-1][disp],t);  
    }  
    dp[i][a[i]-k*b[i]+off]=max(a[i],dp[i][a[i]-k*b[i]+off]);  
  }cout<<(dp[n-1][off]<=0?-1:dp[n-1][off])<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission