NYOJ 737 石子合并（一）（区间DP+平行四边形优化） - c++编程基础

TOP

NYOJ 737 石子合并（一）（区间DP+平行四边形优化）

2015-11-21 01:03:53 来源: 作者: 【大中小】浏览:1次

定义状态dp [ i ] [ j ]为从第i个石子到第j个石子的合并最小代价。
没有优化的代码如下：耗时248ms。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            #include 
           
             using namespace std; #define LL long long #define pi acos(-1.0) //#pragma comment(linker, "/STACK:1024000000") const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-3; const int MAXN=40000+10; int dp[300][300], sum[300]; int main() { int n, i, j, k, len, x; while(scanf("%d",&n)!=EOF) { sum[0]=0; memset(dp,INF,sizeof(dp)); for(i=1; i<=n; i++) { scanf("%d",&x); sum[i]=sum[i-1]+x; dp[i][i]=0; } for(len=2; len<=n; len++) { for(i=1; i<=n-len+1; i++) { j=i+len-1; for(k=i+1; k<=j; k++) { dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j]+sum[j]-sum[i-1]); } } } printf("%d\n",dp[1][n]); } return 0; }

然后这题可以用四边不等式来优化，通过记录s[i][j]的最优分割点为k来将n^3优化成n^2。
优化代码如下：耗时36ms。。。。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            #include 
           
             using namespace std; #define LL long long #define pi acos(-1.0) //#pragma comment(linker, "/STACK:1024000000") const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-3; const int MAXN=40000+10; int dp[300][300], sum[300], s[300][300]; int main() { int n, i, j, k, len, x; while(scanf("%d",&n)!=EOF){ sum[0]=0; memset(dp,INF,sizeof(dp)); for(i=1;i<=n;i++){ scanf("%d",&x); sum[i]=sum[i-1]+x; dp[i][i]=0; s[i][i]=i; } for(len=2;len<=n;len++){ for(i=1;i<=n-len+1;i++){ j=i+len-1; for(k=s[i][j-1];k<=s[i+1][j];k++){ if(dp[i][j]>dp[i][k-1]+dp[k][j]+sum[j]-sum[i-1]){ dp[i][j]=dp[i][k-1]+dp[k][j]+sum[j]-sum[i-1]; s[i][j]=k; } } } } printf("%d\n",dp[1][n]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1204 糖果大战 (Markov Chain..	下一篇：ZOJ 3870 Team Formation（数学）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: