首页 > 代码库 > 石子合并DP
石子合并DP
DP
Time Limit:3000MS Memory Limit:131072KB 64bit IO Format:%lld & %lluDescription
桌上有一排 N 堆饭团。现要将饭团合并成一堆。规则是
每次只能选相邻的 2 堆饭团合并成新的一堆，并将新的一堆饭团数记为这次操作的分数。
将 N 堆饭团合并成一堆的最小总分。
Input
第一行N(N<=40000) 。
以下 每行一个数 x(x<=200) ，表示饭团数目。
Output
输出最小总分。
Sample Input
41111Sample Output
8
//只能 Garsiawachs 解，因为数据很大，时间，空间，一般 DP 都不行
代码看了别人的，代码不难，但是原理难啊，看了很久都不懂。。。先放放，学了哈夫曼树再看看
82ms
1 //GarsiaWachs算法 0ms 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 7 const int N = 40005; 8 int stone[N]; 9 int n,t,ans;10 11 void combine(int k);12 13 int main()14 {15 while(cin>>n)16 {17 for(int i=0;i<n;i++)18 scanf("%d",stone+i);19 t = 1;20 ans = 0;21 for(int i=1;i<n;i++)22 {23 stone[t++] = stone[i];24 while(t >= 3 && stone[t-3] <= stone[t-1])25 combine(t-2);26 }27 while(t > 1)//大于1堆，从最右边那堆开始向左合并28 combine(t-1);29 printf("%d\n",ans);30 }31 return 0;32 }33 void combine(int k)34 {35 int tmp = stone[k] + stone[k-1];36 ans += tmp;37 for(int i=k;i<t-1;i++)//后面的往前移，移到位置 k38 stone[i] = stone[i+1];39 t--;40 41 int j = 0;42 for(j=k-1;j>0 && stone[j-1] < tmp;j--)//厉害了，不断往前移坑，43 stone[j] = stone[j-1];44 stone[j] = tmp;//填坑45 46 while(j >= 2 && stone[j] >= stone[j-2])//如果调整后，又比前2个大，即又是那个条件达成了47 {48 int d = t - j;//记录与堆数的差值49 combine(j-1);50 j = t - d;//少了几堆就向前移动了几次，位置也变为几51 }52 }
石子合并DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。