SPOJ 345 - Mixtures 区间动态规划-白红宇

SPOJ 345 - Mixtures 区间动态规划

阅读量：5019 次

发布时间：2019-06-12

本文共 1306 字，大约阅读时间需要 4 分钟。

有n个混合物排成一排，每个混合物有一个颜色值0<=color<=99，

规定合并只能合并相邻两个，

将颜色a的混合物与颜色b的混合物合并后，颜色为( a+b ) % 100，并产生a*b的污染，

现在要将所有混合物合并，问产生污染的最小值。

【区间动规】很经典的区间动规

dp[i][j] = min { dp[i][k] + dp[k+1][j] + sum[i][k]*sum[k+1][j] }

具体的DP次序详见代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num,len;bool flag;int dp[105][105],sum[105][105],a[105];int main(){ while (~scanf("%d",&n)) { for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<=n;i++) { sum[i][i]=a[i]; for (j=i+1;j<=n;j++) { sum[i][j]=(sum[i][j-1]+a[j])%100; } } memset(dp,-1,sizeof(dp)); for (i=1;i<=n;i++) dp[i][i]=0; for (i=n;i>=1;i--)//枚举左端点 { for (j=i+1;j<=n;j++)//枚举右端点 { for (k=i;k<=j-1;k++)//枚举中间结点 { if (dp[i][j]==-1) dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][k]*sum[k+1][j]; else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][k]*sum[k+1][j]); } } } printf("%d\n",dp[1][n]); } return 0;}