题目的意思是给你n头狼,然后他们自己有a点攻击,附带b点攻击。在每次攻击一头狼时,旁边两条狼会将附带伤害值加到当前狼上。

意味着你会受到ai+bi-1+bi+1点攻击伤害。求杀死所有的狼你受到的伤害最小值。

比赛的时候觉得dp不好做,因为以前没有接触过区间dp,所以一直拿着贪心在乱搞。

区间dp,对区间长度从1到n,进行dp。随着区间长度的增加,所以遍历的次数可以为:

n-len+1

每次遍历的区间最大值应该是:

i+len-1

最小值是每次的起始本身。

然后假设我们攻击这个区间内任意一只狼,这时相当于其它狼已经被消灭。所以dp方程为:

dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);

dp[i][j]意味着从第i头狼攻击到第j头狼的最小伤害值。大概就是下面这个样子:

image.png


#include <iostream>

#include <cstdio>

#include <memory.h>

using namespace std;

const int inf=0x3f3f3f3f-10;

const int maxn = 210;

int a[maxn], b[maxn], dp[maxn][maxn];

int t, n;


int main()

{

    scanf("%d", &t);

    for(int cas=1;cas<=t;cas++){

        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]);

        }

        b[0]=b[n+1]=0;

        for(int i=1;i<=n;i++){

            for(int j=i;j<=n;j++){

                dp[i][j]=inf;

            }

        }

        for(int i=0;i<=n;i++){

            dp[0][i]=dp[i][n+1]=0;

        }

        for(int len=1;len<=n;len++){        //长度为len

            for(int i=1;i<=n-len+1;i++){

                int j=i+len-1;              //遍历长度为len时的区间

                for(int k=i;k<=j;k++){      //区间内应该攻击第k只狼(假设其他狼已经died)

                    dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);

                }

            }

        }

        printf("Case #%d: %d\n", cas, dp[1][n]);

    }

    return 0;

}