学步园

我是一个半月前看到这道题才知道什么是区间DP的。o(╯□╰)o

dp[i][j]表示率先[i,j]区间内的狼所消耗的最小代价，因为这个区间以外的狼还是存活的，所以要加上b[i-1]，b[j+1]，对于dp[1][N]，因为b[0]，b[N+1]=0所以没影响。

dp[i][j]=min dp[i][k-1]+a[k]+dp[k+1][j]+b[i-1]+b[j+1] for i<=k<=j

因为递推的化涉及到后面的区间不知道怎么写，就写了个记忆化搜索，后来看到acmicpc.info的题解，换个枚举方法就可以了Orz

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<ctype.h>
#include<map>
#include<time.h>
#include<bitset>
using namespace std;
//hdu 5115

const int maxn=220;
int T;
int N;
int a[maxn];
int b[maxn];
int dp[maxn][maxn];
bool vis[maxn][maxn];
int dfs(int i,int j)
{
    if(i>j)
    {
        return 0;
    }
    if(vis[i][j]==true)
    {
         return dp[i][j];
    }
    int ans=0x3f3f3f3f;
    for(int k=i;k<=j;k++)
    {
        ans=min(ans,dfs(i,k-1)+a[k]+dfs(k+1,j)+b[i-1]+b[j+1]);
    }
    vis[i][j]=true;
    dp[i][j]=ans;
    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
    return dp[i][j];
}
int main()
{
    freopen("input.txt","r",stdin);
    //freopen("data.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        scanf("%d",&N);
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=N;i++)
        {
            dp[i][i]=a[i]+b[i-1]+b[i+1];
            vis[i][i]=true;
        }
        printf("Case #%d: %d\n",ca,dfs(1,N));//开始写成了I64d，然后输出了很大的数==
    }
    return 0;
}