[题解] HDU 5115 Dire Wolf 区间DP

考虑先枚举所有的物品中最后拿走的，这样就分成了2个子问题，即先拿完左边的，再拿完右边的，最后拿选出的那个。令dp(i,j)表示拿完[i,j]所有物品的最小代价。你可能会说，我们拿[i,j]这一段物品的时候，i左边和j右边的第一个物品可能会不断变化，影响i和j的最终价格。其实是不会的，还是想想一开始说的整个序列枚举最后被拿走的，然后不断分割成子问题的过程，我们都是先拿走[i,j]中的所有元素，之后才会去动i-1或者j+1。所以可以澄清一下dp状态含义：dp(i,j)表示原序列中把[i,j]中的元素全拿完，其他元素全不动的最小代价。转移就很简单了，枚举区间最后被拿走的元素即可。

点击查看代码

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)

#define repn(i,n) for(int i=1;i<=n;++i)

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

int t,n,a[510],b[510],dp[510][510];

int dfs(int lb,int ub)

{

  if(lb>ub) return 0;

  if(dp[lb][ub]<1e9) return dp[lb][ub];

  if(lb==ub) return dp[lb][ub]=a[lb]+(lb==0 ? 0:b[lb-1])+(lb==n-1 ? 0:b[lb+1]);

  for(int i=lb;i<=ub;++i) dp[lb][ub]=min(dp[lb][ub],dfs(lb,i-1)+dfs(i+1,ub)+a[i]+(lb==0 ? 0:b[lb-1])+(ub==n-1 ? 0:b[ub+1]));

  return dp[lb][ub];

}

int main()

{

  freopen("buy.in","r",stdin);

  freopen("buy.out","w",stdout);

  repn(tn,1)

  {

    scanf("%d",&n);

    rep(i,n) scanf("%d",&a[i]);

    rep(i,n) scanf("%d",&b[i]);

    rep(i,n) rep(j,n) dp[i][j]=1e9;

    printf("%d\n",dfs(0,n-1));

  }

	return 0;

}

巴特西

[题解] HDU 5115 Dire Wolf 区间DP

最新文章

热门文章