P1880 [NOI1995]石子合并

admin

https://www.luogu.org/problemnew/show/P1880

题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例
输入样例#1：
4
4 5 9 4
输出样例#1：
43
54

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[250],fax[250][250],fin[250][250],sum[250][250],ans1,ans2;
   
4. int i,j,k;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(i=1;i<=n;i++)
   
9.     {
   
10.         cin>>a[i];a[i+n]=a[i];
    
11.     }
    
12.     /*for(i=1;i<=n+n;i++)
    
13.         cout<<a[i]<<" ";
    
14.     cout<<endl;
    
15.     cout<<"step1"<<endl;*/
    
16.     for(j=1;j<=n;j++)
    
17.         for(i=1;i<=n+n;i++)
    
18.     {
    
19.         if(i+j>n+n+1)break;
    
20.         for(k=i;k<=i+j-1;k++)
    
21.             sum[i][j]+=a[k];
    
22.         ///cout<<sum[i][j]<<" ";
    
23.     }
    
24.     ///cout<<endl;
    
25.     ///cout<<"step2"<<endl;
    
26.     for(j=2;j<=n;j++)
    
27.     {
    
28.         for(i=1;i<=n+n;i++)
    
29.         {
    
30.             if(i+j>n+n+1)break;
    
31.             fin[i][j]=99999;
    
32.             for(k=1;k<j;k++)
    
33.             {
    
34.                 fax[i][j]=max(fax[i][j],fax[i][k]+fax[i+k][j-k]+sum[i][k]+sum[i+k][j-k]);
    
35.                 fin[i][j]=min(fin[i][j],fin[i][k]+fin[i+k][j-k]+sum[i][k]+sum[i+k][j-k]);
    
36.             }
    
37.             ///cout<<j<<" "<<i<<" "<<fax[i][j]<<" "<<fin[i][j]<<endl;
    
38.         }
    
39.     }
    
40.     ans1=99999;
    
41.     for(i=1;i<=n;i++)
    
42.     {
    
43.         ans1=min(ans1,fin[i][n]);
    
44.         ans2=max(ans2,fax[i][n]);
    
45.     }
    
46.     cout<<ans1<<endl<<ans2;
    
47.     return 0;
    
48. }
    

复制代码

admin

楼上的闻同学 你的做法是标准的做法 很好！

universehyf

参加夏令营前写的代码，区间DP，把关键语句写错了。

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <cstring>
   
4. using namespace std;
   
5. const int mm = 202;
   
6. int d[mm], f[mm][mm], g[mm][mm], sum[mm];
   
7. int n, i, j, k, maxn, minn, m;
   
8. int main()
   
9. {
   
10.     cin >> n;
    
11.     for (i = 1; i <= n; i++) cin >> d[i];
    
12.     for (i = 1; i <= n; i++) d[i + n] = d[i];
    
13.     m = n * 2;/*
    
14.     for (i = 1; i <= m; i++)
    
15.         for (j = 1; j <= m - i + 1; j++) g[j][i + j - 1] = 9999999;*/
    
16.     memset(g, 0x3f3f3f3f, sizeof(g));
    
17.     for (i = 1; i <= m; i++) f[i][i] = g[i][i] = 0;
    
18.     for (i = 1; i <= m; i++) sum[i] = sum[i - 1] + d[i];
    
19.     for (i = 2; i <= n; i++)
    
20.         for (j = 1; j <= m - i; j++)
    
21.             for (k = j; k <= i + j - 2; k++)
    
22.             {
    
23.                 f[j][i + j - 1] = max(f[j][i + j - 1], f[j][k]+f[k + 1][i + j - 1] + sum[i + j - 1] - sum[j - 1]);
    
24.                 g[j][i + j - 1] = min(g[j][i + j - 1], g[j][k]+g[k + 1][i + j - 1] + sum[i + j - 1] - sum[j - 1]);
    
25.                 //if (i == n) cout << f[j][i + j - 1] << ' ' << g[j][i + j - 1] << endl;
    
26.             }
    
27.     maxn = 0;
    
28.     minn = 9999999;
    
29.     for (i = 1; i <= n; i++)
    
30.     {
    
31.         if (f[i][i + n - 1] > maxn) maxn = f[i][i + n - 1];
    
32.         if (g[i][i + n - 1] < minn) minn = g[i][i + n - 1];
    
33.     }
    
34.     cout << minn << endl
    
35.          << maxn;
    
36.     return 0;
    
37. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstring>
   
4. using namespace std;
   
5. int n,a[201];
   
6. int dp1[201][201],dp2[201][201];
   
7. int s[201];
   
8. int dis(int x,int y)
   
9. {
   
10.     return s[y]-s[x-1];
    
11. }
    
12. int main()
    
13. {
    
14.     cin>>n;
    
15.     for(int i=1; i<=n; i++)
    
16.     {
    
17.         cin>>a[i];
    
18.         a[i+n]=a[i];
    
19.     }
    
20.     for(int i=1; i<=(n<<1); i++)s[i]=s[i-1]+a[i];
    
21.     for(int i=(n<<1)-1; i>=1;i--)
    
22.         for(int j=i+1; j<i+n; j++)
    
23.         {
    
24.             if(j>n<<1)continue;
    
25.             dp1[i][j]=999999;
    
26.             for(int k=i; k<j; k++)
    
27.             {
    
28.                 dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+dis(i,j));
    
29.                 dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+dis(i,j));
    
30.             }
    
31.         }
    
32.     int minx=99999999,maxx=-1;
    
33.     for(int i=1;i<=n;i++)
    
34.     {
    
35.         minx=min(dp1[i][i+n-1],minx);
    
36.         maxx=max(dp2[i][i+n-1],maxx);
    
37.     }
    
38.     cout<<minx<<endl<<maxx;
    
39.     return 0;
    
40. }
    

复制代码

admin

楼上何同学，代码风格不错！

张笑宇

区间DP

1. #include<iostream>
   
2. using namespace std;
   
3. int n;
   
4. const int mx=210;
   
5. int a[mx],i,j,k,s[mx];///s前缀和
   
6. int dpmin[mx][mx],dpmax[mx][mx];
   
7. int main()
   
8. {
   
9.     cin>>n;
   
10.     for (i=1; i<=n; i++) cin>>a[i],a[i+n]=a[i];
    
11.     for (i=1; i<=2*n; i++) s[i]=s[i-1]+a[i];
    
12.     for (i=2*n-1; i>=1; i--)
    
13.         for (j=i+1; j<=i+n-1; j++)
    
14.         {
    
15.             dpmin[i][j]=9999999;
    
16.             dpmax[i][j]=-9999999;
    
17.             for (k=i; k<=j-1; k++)
    
18.             {
    
19.                 dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+s[j]-s[i-1]);
    
20.                 dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+s[j]-s[i-1]);
    
21.             }
    
22.         }
    
23.     int ansmax=-99999,ansmin=99999;
    
24.     for (i=1; i<=n; i++)
    
25.     {
    
26.         ansmax=max(ansmax,dpmax[i][i+n-1]);
    
27.         ansmin=min(ansmin,dpmin[i][i+n-1]);
    
28.     }
    
29.     cout<<ansmin<<endl<<ansmax;
    
30.     return 0;
    
31. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. int n,m;
   
5. int v[501],sum[501];
   
6. int fmin[501][501];
   
7. int fmax[501][501];
   
8. int maximum=-999999,minimum=999999;
   
9. int main()
   
10. {
    
11.         scanf("%d",&n);
    
12.         for(int i=1;i<=n;i++)
    
13.         {
    
14.                 scanf("%d",&v[i]);
    
15.                 v[i+n]=v[i];
    
16.         }
    
17.         for(int i=1;i<=n<<1;i++)
    
18.                 sum[i]=sum[i-1]+v[i];
    
19.         for(int i=2*n-1;i>=1;i--)
    
20.                 for(int j=i+1;j<=i+n-1;j++)
    
21.                 {
    
22.                         fmin[i][j]=minimum;       
    
23.                         for(int k=i;k<j;k++)
    
24.                         {
    
25.                                 fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]);
    
26.                                 fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]);
    
27.                         }
    
28.                 }
    
29.         for(int i=1;i<=n;i++)
    
30.         {
    
31.                 minimum=min(minimum,fmin[i][i+n-1]);
    
32.                 maximum=max(maximum,fmax[i][i+n-1]);
    
33.         }
    
34.         printf("%d\n%d",minimum,maximum);
    
35.         return 0;
    
36. }

复制代码