---
title: Codeforce 366 C. Dima and Salad 解析(思維、DP)
description: "Codeforce 366 C. Dima and Salad 解析(思維、DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 366 C. Dima and Salad 解析(思維、DP)">
<!-- toc -->

# Codeforce 366 C. Dima and Salad 解析(思維、DP)
今天我們來看看CF366C
[題目連結](https://codeforces.com/problemset/problem/366/C)

> **題目**
略。直接看原題即可

### 前言
覺得可能是用到類似$\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](https://codeforces.com/contest/366/submission/90734240)