首页 > 代码库 > Dire Wolf

Dire Wolf

2024-08-05 22:20:56   216人阅读

·网上说是区间dp，但不是很懂；

·看了别人的解题报告与代码，感觉跟分治比较像

 

解释：

　　dp[i][j] 表示 杀从第i头狼到第j头狼所获得的最小伤害；

　   for(int i=l+1;i<r;i++){

           dp[l][r] = min(dp[l][r],dfs(l,i) + dfs(i,r) + a[i] + b[l] + b[r]); // 先选择第i头狼

      }

　　其中的递推式，是从l+1 ~ r-1 之间，选择先杀某一头狼。  

 

AC Code：

 1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <cstring> 5 #include <string.h> 6 #include <math.h> 7 #include <queue> 8 #include <stack> 9 #include <stdlib.h>10 #include <map>11 using namespace std;12 #define LL long long 13 #define sf(a) scanf("%d",&(a));14 //区间dp ： f[i][j]代表，从第i个狼到第j个狼，最优策略（感觉有点像分治）15 #define N 22016 int a[N],b[N];17 int dp[N][N];18 19 const int INF = 0x3f3f3f3f;20 21 int dfs(int l,int r){22     if(l+1 >= r) return dp[l][r]=0;23     if(dp[l][r] != INF) return dp[l][r];24     for(int i=l+1;i<r;i++){25         dp[l][r] = min(dp[l][r],dfs(l,i) + dfs(i,r) + a[i] + b[l] + b[r]); // 先选择第i头狼26     }27     return dp[l][r];28 }29 30 int main(){31     int k=1,n;32     int T;scanf("%d",&T);33     while(T--){34         //memset(dp,-1,sizeof(dp));35         printf("Case #%d: ",k++);36         for(int i=0;i<N;i++)37             for(int j=0;j<N;j++) dp[i][j] = INF;38         scanf("%d",&n);39         for(int i=1;i<=n;i++) scanf("%d",&a[i]);40         for(int i=1;i<=n;i++) scanf("%d",&b[i]);41         printf("%d\n",dfs(0,n+1));42     }43 44     return 0;45 }

 

Dire Wolf


联系
我们