HDU3506 Monkey Party （区间DP）

一道好题......

首先要将环形转化为线形结构，接着就是标准的区间DP，但这样的话复杂度为O(n³),n<=1000,要超时，所以要考虑优化。

dp[i][j]=min( dp[i][k]+dp[k+1][j]+sum(i,j) ),我们通过证明sum(i,j)满足四边不等式和区间包含单调性，从而dp[i][j]也满足四边不等式，进一步得到对于决策s(i,j),满足s(i,j-1)<=s(i,j)<=s(i+1,j),i<=j. 然后就可以优化到O(n²).

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 using namespace std;

 5 const int INF=0x3f3f3f3f;

 6 const int N=1005;

 7 int n;

 8 int dp[N<<1][N<<1];

 9 int s[N<<1][N<<1];//记录决策点

10 int sum[N<<1];//前缀和

11 int a[N<<1];

12

13 void init(){

14     sum[0]=0;

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

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

17         sum[i]=a[i]+sum[i-1];

18         dp[i][i]=0;//自己认识自己不需要时间

19         s[i][i]=i;

20     }

21     for(int i=1;i<n;i++){//环形处理为线形

22         a[n+i]=a[i];

23         sum[n+i]=a[n+i]+sum[n+i-1];

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

25         s[n+i][n+i]=n+i;

26     }

27 }

28

29 void solve(){

30     for(int d=2;d<=n;d++)

31         for(int i=1;i<=2*n-d;i++){

32             int j=i+d-1;

33             int tmp=sum[j]-sum[i-1];

34             dp[i][j]=INF;

35             for(int k=s[i][j-1];k<=s[i+1][j];k++)//四边不等式优化

36                 if(dp[i][k]+dp[k+1][j]+tmp<dp[i][j]){

37                     dp[i][j]=dp[i][k]+dp[k+1][j]+tmp;

38                     s[i][j]=k;//记录决策点

39                 }

40         }

41     int ans=INF;

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

43         ans=min(ans,dp[i][n+i-1]);

44     printf("%d\n",ans);

45 }

46

47 int main(){

48     while(~scanf("%d",&n)){

49         init();

50         solve();

51     }

52     return 0;

53 }

HDU3506 Monkey Party （区间DP）的相关教程结束。