首页 > 代码库 > 洛谷 P1880 石子合并
洛谷 P1880 石子合并
题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1：
44 5 9 4
输出样例#1：
4354
解题思路
由于是环形的，所以我们把石子复制一遍，比如5堆石子，从第4堆环形合并到第3堆(4、5、1、2、3)，复制后石子编号就是4 5 6 7 8了，复制一遍就能拆环，直接当做两倍长的链处理。
在这条链上，用动规数组f[j][i](代码风格太迷，一不小心反了)表示第i堆到第j堆所得积分的极值，它等于i到j的石子总数加已得积分的极值。比如要求2~5的积分，我们可以通过这么几种方式合并出2~5—— 2+3~5 2~3+4~5 2~4+5。求出这几种方式哪种能得到最多或最少的积分，一路求下去直到全部合成一堆为止。
源代码
#include<stdio.h>#include<string.h>int a[210]={0};int f[210][210]={0};int s[210]={0};int n,ans;inline int max(int a,int b){ return a>b?a:b;}inline int min(int a,int b){ return a<b?a:b;}void print(){ for(int i=1;i<=n<<1;i++) { for(int j=1;j<=n<<1;j++) printf("%4d",f[i][j]); printf("\n"); } printf("\n");}int main(){ //freopen("test.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),s[i]=s[i-1]+a[i]; for(int i=n+1;i<=n<<1;i++) s[i]=s[i-1]+a[i-n]; memset(f,0,sizeof(f)); for(int i=2;i<=n;i++) { int c=i-1; for(int j=1;j<=(n<<1)-c;j++) { int minn=999999999; f[j+c][j]=s[j+c]-s[j-1]; if(c==1) minn=0; for(int k=0;k<c;k++) minn=min(minn,f[j+k][j]+f[j+c][k+j+1]); f[j+c][j]+=minn; }//print(); } ans=999999999; for(int i=n;i<=n<<1;i++) ans=min(ans,f[i][i-n+1]); printf("%d\n",ans); memset(f,0,sizeof(f)); for(int i=2;i<=n;i++) { int c=i-1; for(int j=1;j<=(n<<1)-c;j++) { int maxn=-1; f[j+c][j]=s[j+c]-s[j-1]; if(c==1) maxn=0; for(int k=0;k<c;k++) maxn=max(maxn,f[j+k][j]+f[j+c][k+j+1]); f[j+c][j]+=maxn; }//print(); } ans=-1; for(int i=n;i<=n<<1;i++) ans=max(ans,f[i][i-n+1]); printf("%d",ans); return 0;}
Ps：
这题半年前就想写了，但由于码力不足，一直没动，今晚总算把它a了。
现在时间：2017年06月03日02:26:43。凌晨做题真有意思，总是想睡觉又想切了这题再睡。
由于状态转移掌握不太熟，一个状态从哪些情况转移过来(代码里的第三重循环)，脑子不清楚，于是那段我是"调参"调出来的，我这种写法细节要注意的太多了……网上其他题解的状态转移写的真心简洁，循环方式也不同，代码量就少了很多，以后还要多多学习呀
洛谷 P1880 石子合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。