区间DP get！
A4paper
·
·
个人记录
入门：
传送门
先初始化 $f[i][i] = a[i]*n$ ，只选一份零食的情况下当然是在第 $n$ 天价值最大
**状态转移方程：**
```cpp
f[L][R] = max(f[L][R-1]+a[R]*(n-k+1),f[L+1][R]+a[L]*(n-k+1));
```
在 $L$ 到 $R$ 的区间最值等于比它短 1 的区间加上右端点或左端点的最大值。
$n-k+1$ 是天数，由于一开始处理的是最大值，所以这其实是一个倒序的过程，从最后一天转移到第一天。
为什么要倒序呢？可以这么想，正序的话是每次拿走两端的零食，然而拿走的顺序又与中间一些零食有关，直接做是不好做的，所以要倒过来考虑。
这时候就只剩下**最后一个问题**
**为什么 $L$ 要倒着 $for$ ？**
参考转移方程，想要转移到下一个状态，我们需要知道 $L$ 到 $R-1$ 以及 $L+1$ 到 $R$ ，其中， $L$ 到 $R-1$ 是之前就处理出来了的，而 $L+1$ 到 $R$ 则必须由之前一层 $for$ 循环过程中处理出来，所以 $L$ 的顺序是要从 $L+1$ 到 $L$ 即倒着跑。
```cpp
int f[MAXN][MAXN];
int main(void)
{
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) f[i][i] = a[i]*n;
for(int L=n;L>=1;L--)
for(int k=1;k<=n;k++)
{
int R = L+k-1;
if(R > n) break;
f[L][R] = max(f[L][R-1]+a[R]*(n-k+1),f[L+1][R]+a[L]*(n-k+1));
}
cout << f[1][n];
return 0;
}
```
# 普通：
[传送门](https://www.luogu.org/problemnew/show/P1435)
```cpp
int f[1005][1005];
char len[1005];
int n;
int main()
{
scanf("%s",len);
n = strlen(len);
for(int k=1;k<=n;k++)
for(int i=0;i<n-1,i+k<n;i++)
{
int j = i+k;
if(len[i] == len[j]) f[i][j] = f[i+1][j-1];
else f[i][j] = min(f[i+1][j],f[i][j-1])+1;
}
cout << f[0][n-1];
return 0;
}
```
# 进阶：
[传送门](https://www.luogu.org/problemnew/show/P1063)
```cpp
int n;
int maxn = 0;
int a[1050];
int dp[1050][1050];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
a[i+n] = a[i];
}
for(int j=2;j<=n*2;j++)
for(int i=j-1;j-i<n && i>0;i--)
{
for(int k=i;k<j;k++)
dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
if(maxn < dp[i][j]) maxn = dp[i][j];
}
cout << maxn;
return 0;
}
```
# 多维：
[传送门](https://www.luogu.org/problemnew/show/P3080)
其实，这道题与[另一道题](https://www.luogu.org/problemnew/show/P1220#sub)是一样的。
$f[L][R][2]$ 表示左端点为 $L$ ，右端点为 $R$ ，第三维为 0 时表示 $FJ$ 停在了左端点，为 1 时在右端点，的最小费用。
```cpp
int n,mid;
int f[MAXN][MAXN][2];
int meter[MAXN];
int val[MAXN];
int w(int L, int R, int l, int r)
{
return (L-1+n-R)*(meter[r]-meter[l]);
}
int main(void)
{
memset(f,0x3f,sizeof f);
cin >> n;
for(int i=1;i<=n;i++) cin >> meter[i];
meter[++n] = 0;
sort(meter+1,meter+1+n);
for(int i=1;i<=n;i++)
if(meter[i] == 0)
{
mid = i;
break;
}
f[mid][mid][0] = f[mid][mid][1] = 0;
for(int R=mid;R<=n;R++)
for(int L=R-1;L>=1;L--)
{
f[L][R][0] = min(f[L+1][R][0]+w(L+1,R,L,L+1),f[L+1][R][1]+w(L+1,R,L,R));
f[L][R][1] = min(f[L][R-1][1]+w(L,R-1,R-1,R),f[L][R-1][0]+w(L,R-1,L,R));
}
cout << min(f[1][n][1],f[1][n][0]);
return 0;
}
```
# 博弈：
[传送门](https://www.luogu.org/problemnew/show/P2734)
乍一看，这不博弈吗？先找必胜态。。。
后来发现哪里不对劲，这其实是一道区间 $DP$ 。
但是，这与普通的区间 $DP$ 不同，要换一个思路去理解，
首先，作为区间 $DP$ 肯定是要先开二维数组 $f[i][j]$ 表示从 $i$ 到 $j$ 能拿到的最大值，不过值得注意的是， $f$ 数组只表示一个最大值，而不是玩家一或玩家二的值，因为每个人都会取最优决策，所以这个状态会在两个人间来回换（我也说不清楚，感性理解一下）
那么状态转移方程就是：
```cpp
f[i][j] = max(s[j]-s[i-1]-f[i+1][j],s[j]-s[i-1]-f[i][j-1]);
```
其中 $s$ 表示前缀和，方程的意义就是区间总和减去上一步的最值，这是一个倒推的过程，就是已经选好了 $i+1$ 到 $j$ 或 $i$ 到 $j-1$ 的数，现在要选 $i$ 或 $j$ 时的最优值。
```cpp
int main(void)
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> s[i];
f[i][i] = s[i];
s[i] += s[i-1];
}
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++)
f[i][j] = max(s[j]-s[i-1]-f[i+1][j],s[j]-s[i-1]-f[i][j-1]);
cout << f[1][n] << " " << s[n]-f[1][n];
return 0;
}
```