首页 > 代码库 > 石子合并

石子合并

2024-07-06 10:16:02   224人阅读

石子合并
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 96   Accepted: 48

Description

在操场上沿一直线排列着 
n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆， 
并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。 

计算在上述条件下将n堆石子合并成一堆的最小得分。 

Input

输入数据共有二行，其中，第1行是石子堆数n≤100； 

第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格分隔。 

Output

输出合并的最小得分。

Sample Input

3 2 5 1

Sample Outpu

11

 

分析：设sum[i]为前i个石子的总分，dp[i][j]为i到j之间最小得分。

        则可得状态转移方程dp[i][j]=min{dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]};

       枚举对调位置，找出最小得分。

 

代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 #define MAX 0x7fffffff/2
 6 int dp[110][110], n, a[110], w[110], ans;
 7 
 8 int dpp()
 9 {
10     int i, j, l, k;
11     w[0]=0;
12     
13     for(i=0;i<101;i++)
14     for(j=0;j<101;j++)
15     dp[i][j]=MAX;
16     for(i=1;i<=n;i++){
17         w[i]=w[i-1]+a[i];
18         dp[i][i]=0;
19     } 
20     for(i=n-1;i>=1;i--)
21     {
22         for(l=1;l<=n-i;l++)
23         {
24             j=l+i;
25             for(k=i;k<j;k++)
26             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[j]-w[i-1]);
27         }
28     }
29     if(ans>dp[1][n])
30     ans=dp[1][n];
31     return ans;
32 }
33 
34 main()
35 {
36     int i, j;
37     scanf("%d",&n);
38     for(i=1;i<=n;i++) scanf("%d",&a[i]);
39     ans=MAX;
40     dpp();
41     for(i=1;i<n;i++)
42     {
43         swap(a[i],a[i+1]);
44         dpp();
45         swap(a[i],a[i+1]);
46     }
47     printf("%d\n",ans);
48 }

 


联系
我们