題目：洛谷P5858 「SWTR-03」Golden Sword
看完題，就感覺是用dp解決庐完，和背包問(wèn)題有點(diǎn)像长捧。如果簡(jiǎn)單地用f[i]表示放入第i種原料時(shí)寶劍的最大耐久度领跛，顯然不滿足無(wú)后效性核蘸，因?yàn)閷?duì)于一個(gè)耐久度是負(fù)數(shù)的材料谒拴，它需要鍋里的材料盡可能少尝江；反之對(duì)于大耐久度的材料，它需要鍋里的材料盡可能多英上。如果遇上負(fù)耐久的一股腦的全拿走炭序，后面有大的正耐久度的材料啤覆，總耐久度就不大了；如果一直不取惭聂，后面來(lái)一個(gè)負(fù)的大耐久窗声，總耐久也不是最大。
如何消除后效性辜纲，做法之一就是給狀態(tài)加一維笨觅，變成f(i,j)，表示第i個(gè)材料耕腾，當(dāng)鍋里有j個(gè)材料時(shí)见剩，寶劍最大耐久度。這樣的話后效性就被消除了扫俺，變成了無(wú)后效性苍苞，最終結(jié)果就是max(f(n,k)),k屬于[1,w]。轉(zhuǎn)移方程：
f(i,j)=max(f(i-1,k)+a[i]*j)狼纬，k屬于[max(j-1,1)羹呵，min(i-1, j+s-1,w)]
因?yàn)樵诜湃氲趇個(gè)材料時(shí)，如果一個(gè)都不取出疗琉，那么放第i-1個(gè)材料時(shí)候鍋里有j-1個(gè)冈欢，加上新放入的第i個(gè)，正好是j個(gè)没炒；如果取出s個(gè)涛癌，那么說(shuō)明原來(lái)有j-1+s個(gè)犯戏。
j最大就是w送火，因?yàn)殄伬镏荒芊舧個(gè)，先手畫圖感受一下樣例3：
7 4 2
-5 3 -1 -4 7 -6 5
| x | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | -5 | |||
| 2 | -2 | 1 | ||
| 3 | 0 | -1 | -2 | |
| 4 | -4 | -8 | -13 | -18 |
| 5 | 3 | 10 | 13 | 15 |
| 6 | 4 | 1 | -3 | -9 |
| 7 | 9 | 14 | 16 | 17 |
根據(jù)此方程寫出代碼：
#include <cstdio>
#include <climits>
#include <algorithm>
#define MAX 5500
typedef long long ll;
using namespace std;
int n, w, s, a[MAX+1];
ll f[MAX+1][MAX+1];
void dp(){
f[1][1] = a[1];
for(int i = 2; i <= n; i++){
for(int j = 1; j <= min(i, w); j++){
//當(dāng)?shù)趇個(gè)材料放到鍋里以后先匪，形成了j個(gè)种吸，那么原來(lái)可能有多少個(gè)？
//原來(lái)有j-1個(gè)呀非，不用取坚俗，直接放入1個(gè)，就形成了j岸裙，原來(lái)不可能有0個(gè)
//原來(lái)有j-1+s個(gè)猖败，取走s，再放入1個(gè)降允，就形成了j恩闻，原來(lái)不可能有大于w個(gè)
ll m = LLONG_MIN;
for(int k = max(j-1, 1); k <= min(i-1, min(j-1+s, w)); k++){
ll tmp = f[i-1][k];
if (m < tmp){
m = tmp;
}
}
f[i][j] = m + (ll)a[i] * j;
}
}
}
int main(){
scanf("%d%d%d", &n, &w, &s);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
}
dp();
ll ans = LLONG_MIN;
for(int i = 1; i <= w; i++){
ans = max(ans, f[n][i]);
}
printf("%lld\n", ans);
return 0;
}
單調(diào)隊(duì)列優(yōu)化
上面做法由于3層循環(huán)，復(fù)雜度是O(n(w平方))剧董，只能85分幢尚，當(dāng)s和w很大時(shí)候破停，出不來(lái)結(jié)果。
考慮優(yōu)化尉剩，最外層循環(huán)肯定不能優(yōu)化真慢，總要從1看到n，內(nèi)層兩個(gè)循環(huán)理茎，可以看成是一個(gè)大小為s+1的窗口（取的數(shù)目是[0,s]黑界，所以窗口大小是s+1）不斷向右滑動(dòng)，每次設(shè)置f(i,j)時(shí)都是取出這個(gè)窗口里的最大值功蜓，使用單調(diào)隊(duì)列园爷，可以將內(nèi)層兩個(gè)循環(huán)的復(fù)雜度從w平方變成w。
#include <cstdio>
#include <climits>
#include <algorithm>
#define MAX 5500
typedef long long ll;
using namespace std;
int n, w, s, a[MAX+1];
ll f[MAX+1][MAX+1];
int q[MAX], qi, qj;
void dp(){
f[1][1] = a[1];
for(int i = 2; i <= n; i++){
qi = qj = 0;//初始化單調(diào)隊(duì)列
//把1到s-1入隊(duì)式撼，肯定不需要隊(duì)頭出隊(duì)
int last;
for(last = 1; last < s && last <= i - 1; last++){
while(qi < qj && f[i-1][q[qj-1]] <= f[i-1][last]){
qj--;
}
q[qj++] = last;
}
last--;
for(int j = 1; j <= min(i, w); j++){
int st = max(j-1, 1);
if (qi < qj && q[qi] < st){
qi++;
}
int end = min(i-1, min(w, j - 1 + s));
if (last < end){
while(qi < qj && f[i-1][q[qj-1]] <= f[i-1][last+1]){
qj--;
}
q[qj++] = (++last);
}
f[i][j] = f[i-1][q[qi]] + (ll)a[i] * j;
}
}
}
int main(){
scanf("%d%d%d", &n, &w, &s);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
}
dp();
ll ans = LLONG_MIN;
for(int i = 1; i <= w; i++){
ans = max(ans, f[n][i]);
}
printf("%lld\n", ans);
return 0;
}
