UVALive 7061 Dire Wolf 区间dp

题意：

有一个猎人和n匹狼

每个狼有一个自己的攻击力a[i]

每一个狼还有一个buff 可以给旁边的狼加b[i]攻击力

如果这匹狼被消灭了那么这个buff也就不存在了

猎人每消灭一个狼会受到等同于攻击力的伤害

问猎人消灭所有的狼能受到的最少伤害

思路：

经典区间dp

如果我们要消灭第[l,r]区间中狼i 那么我们的消耗就是

dfs(l,i-1)+dfs(i+1,r)+a[i]+b[l-1]+b[r+1]

整体深搜一遍就行了~

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(a) cerr<<#a<<"=="<<a<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair<int,int> pii;
 7 
 8 const int maxn=200+10;
 9 const int inf=0x3f3f3f3f;
10 
11 int a[maxn],b[maxn];
12 int dp[maxn][maxn];
13 
14 int dfs(int l,int r)
15 {
16     if(l>r) return 0;
17     if(dp[l][r]<inf) return dp[l][r];
18     for(int i=l;i<=r;i++)
19     {
20         dp[l][r]=min(dp[l][r],dfs(l,i-1)+dfs(i+1,r)+a[i]+b[l-1]+b[r+1]);
21     }
22     return dp[l][r];
23 }
24 
25 int main()
26 {
27     int T,cas=1;
28     scanf("%d",&T);
29     while(T--)
30     {
31         int n;
32         scanf("%d",&n);
33         cl(a,0),cl(b,0),cl(dp,inf);
34         for(int i=0;i<n;i++)
35         {
36             scanf("%d",&a[i]);
37         }
38         for(int i=0;i<n;i++)
39         {
40             scanf("%d",&b[i]);
41         }
42         printf("Case #%d: %d
",cas++,dfs(0,n+1));
43     }
44     return 0;
45 }/*
46 
47 2
48 3
49 3 5 7
50 8 2 0
51 10
52 1 3 5 7 9 2 4 6 8 10
53 9 4 1 2 1 2 1 4 5 1
54 
55 */