牛客动态规划课程习题-刷野

题目链接：https://ac.nowcoder.com/acm/problem/210807
题意：有n个怪排成一排，你需要去消灭他们，消灭第i只怪的时候，会受到a[i]+b[i-1]+b[i+1]的伤害，消灭一只后，剩下的的会按原顺序重新战成一排，求最小承受伤害。
题解:区间dp.我们令dp[i][j]为消灭i-j的怪的最小伤害，那么就可以开始转移，最开始先处理好单独消灭每只怪的伤害（这个是固定的），然后在i-j间枚举断点来更新最小伤害。 （不明白具体实现可以看注释）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define paii pair<int,int>
#define fr first
#define sc second
const int maxn=505;
const int inf=0x3f3f3f3f;
int n,a[maxn],b[maxn];
int dp[maxn][maxn];
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d",a+i);
    for (int i=1;i<=n;i++)scanf("%d",b+i);
    a[0]=a[n+1]=b[0]=b[n+1]=0;//可看成在0和n+1的地方都放一个a b为0的怪，方便后续转移
    for (int i=1;i<=500;i++)
        for (int j=1;j<=500;j++)
            if (j<i)dp[i][j]=0;//无意义的状态，但是在下面循环k的时候可能出现，初始化为0避免影响
            else
            dp[i][j]=inf;//初始化最大值
    for (int i=1;i<=n;i++)dp[i][i]=a[i]+b[i-1]+b[i+1];
    for (int len=2;len<=n;len++){//枚举区间长度，所以每次转移的子状态都已经计算好了
        for (int i=1;i<=n;i++){
            int j=i+len-1;
            if (j>n)continue;
            for (int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}