不同 oid stdio.h 其他 += int 我们 ber
在一个园形操场的四周摆放 N 堆石子, 现要将石子有次序地合并成一堆. 规定每次只能选相邻的 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
试设计出 1 个算法, 计算出将 N 堆石子合并成 1 堆的最小得分和最大得分.
输入格式:
数据的第 1 行试正整数 N,1≤N≤100, 表示有 N 堆石子. 第 2 行有 N 个数, 分别表示每堆石子的个数.
输出格式:
输出共 2 行, 第 1 行为最小得分, 第 2 行为最大得分.
输出样例 #1:
- 4
- 4 5 9 4
- 43
- 54
由于是环形的,所以我们把石子复制一遍,比如 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
- #include<string.h>inta[210]={0};
- intf[210][210]={0};
- ints[210]={0};
- int n,ans;
- inline intmax(inta,int b)
- {
- returna>ba:b;
- }
- inline intmin(inta,int b)
- {
- returnaa:b;
- }
- void print()
- {
- for(inti=1;i<=n<<1;i++)
- {
- for(intj=1;j<=n<<1;j++)
- printf("M",f[i][j]);
- printf("n");
- }
- printf("n");
- }
- int main()
- {
- //freopen("test.in","r",stdin);scanf("%d",&n);
- for(inti=1;i<=n;i++)
- scanf("%d",a+i),s[i]=s[i-1]+a[i];
- for(inti=n+1;i<=n<<1;i++)
- s[i]=s[i-1]+a[i-n];
- memset(f,0,sizeof(f));
- for(inti=2;i<=n;i++)
- {
- intc=i-1;
- for(intj=1;j<=(n<<1)-c;j++)
- {
- intminn=999999999;
- f[j+c][j]=s[j+c]-s[j-1];
- if(c==1) minn=0;
- for(intk=0;k)
- minn=min(minn,f[j+k][j]+f[j+c][k+j+1]);
- f[j+c][j]+=minn;
- }//print();
- }
- ans=999999999;
- for(inti=n;i<=n<<1;i++)
- ans=min(ans,f[i][i-n+1]);
- printf("%dn",ans);
- memset(f,0,sizeof(f));
- for(inti=2;i<=n;i++)
- {
- intc=i-1;
- for(intj=1;j<=(n<<1)-c;j++)
- {
- intmaxn=-1;
- f[j+c][j]=s[j+c]-s[j-1];
- if(c==1) maxn=0;
- for(intk=0;k)
- maxn=max(maxn,f[j+k][j]+f[j+c][k+j+1]);
- f[j+c][j]+=maxn;
- }//print();
- }
- ans=-1;
- for(inti=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 石子合并
来源: http://www.bubuko.com/infodetail-2100895.html