华师一附中OI组
标题:
P1880 [NOI1995]石子合并
[打印本页]
作者:
admin
时间:
2018-6-28 19:13
标题:
P1880 [NOI1995]石子合并
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
作者:
倚窗倾听风吹雨
时间:
2018-7-15 11:17
#include<iostream>
using namespace std;
int n,a[250],fax[250][250],fin[250][250],sum[250][250],ans1,ans2;
int i,j,k;
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];a[i+n]=a[i];
}
/*for(i=1;i<=n+n;i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"step1"<<endl;*/
for(j=1;j<=n;j++)
for(i=1;i<=n+n;i++)
{
if(i+j>n+n+1)break;
for(k=i;k<=i+j-1;k++)
sum[i][j]+=a[k];
///cout<<sum[i][j]<<" ";
}
///cout<<endl;
///cout<<"step2"<<endl;
for(j=2;j<=n;j++)
{
for(i=1;i<=n+n;i++)
{
if(i+j>n+n+1)break;
fin[i][j]=99999;
for(k=1;k<j;k++)
{
fax[i][j]=max(fax[i][j],fax[i][k]+fax[i+k][j-k]+sum[i][k]+sum[i+k][j-k]);
fin[i][j]=min(fin[i][j],fin[i][k]+fin[i+k][j-k]+sum[i][k]+sum[i+k][j-k]);
}
///cout<<j<<" "<<i<<" "<<fax[i][j]<<" "<<fin[i][j]<<endl;
}
}
ans1=99999;
for(i=1;i<=n;i++)
{
ans1=min(ans1,fin[i][n]);
ans2=max(ans2,fax[i][n]);
}
cout<<ans1<<endl<<ans2;
return 0;
}
复制代码
作者:
admin
时间:
2018-7-15 13:23
楼上的闻同学 你的做法是标准的做法 很好！
作者:
universehyf
时间:
2018-7-23 23:21
参加夏令营前写的代码，区间DP，把关键语句写错了。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int mm = 202;
int d[mm], f[mm][mm], g[mm][mm], sum[mm];
int n, i, j, k, maxn, minn, m;
int main()
{
cin >> n;
for (i = 1; i <= n; i++) cin >> d[i];
for (i = 1; i <= n; i++) d[i + n] = d[i];
m = n * 2;/*
for (i = 1; i <= m; i++)
for (j = 1; j <= m - i + 1; j++) g[j][i + j - 1] = 9999999;*/
memset(g, 0x3f3f3f3f, sizeof(g));
for (i = 1; i <= m; i++) f[i][i] = g[i][i] = 0;
for (i = 1; i <= m; i++) sum[i] = sum[i - 1] + d[i];
for (i = 2; i <= n; i++)
for (j = 1; j <= m - i; j++)
for (k = j; k <= i + j - 2; k++)
{
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]);
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]);
//if (i == n) cout << f[j][i + j - 1] << ' ' << g[j][i + j - 1] << endl;
}
maxn = 0;
minn = 9999999;
for (i = 1; i <= n; i++)
{
if (f[i][i + n - 1] > maxn) maxn = f[i][i + n - 1];
if (g[i][i + n - 1] < minn) minn = g[i][i + n - 1];
}
cout << minn << endl
<< maxn;
return 0;
}
复制代码
作者:
黄煦喆
时间:
2018-7-29 18:35
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[201];
int dp1[201][201],dp2[201][201];
int s[201];
int dis(int x,int y)
{
return s[y]-s[x-1];
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1; i<=(n<<1); i++)s[i]=s[i-1]+a[i];
for(int i=(n<<1)-1; i>=1;i--)
for(int j=i+1; j<i+n; j++)
{
if(j>n<<1)continue;
dp1[i][j]=999999;
for(int k=i; k<j; k++)
{
dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+dis(i,j));
dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+dis(i,j));
}
}
int minx=99999999,maxx=-1;
for(int i=1;i<=n;i++)
{
minx=min(dp1[i][i+n-1],minx);
maxx=max(dp2[i][i+n-1],maxx);
}
cout<<minx<<endl<<maxx;
return 0;
}
复制代码
作者:
admin
时间:
2018-7-29 18:40
楼上何同学，代码风格不错！
作者:
张笑宇
时间:
2018-7-29 18:46
区间DP
#include<iostream>
using namespace std;
int n;
const int mx=210;
int a[mx],i,j,k,s[mx];///s前缀和
int dpmin[mx][mx],dpmax[mx][mx];
int main()
{
cin>>n;
for (i=1; i<=n; i++) cin>>a[i],a[i+n]=a[i];
for (i=1; i<=2*n; i++) s[i]=s[i-1]+a[i];
for (i=2*n-1; i>=1; i--)
for (j=i+1; j<=i+n-1; j++)
{
dpmin[i][j]=9999999;
dpmax[i][j]=-9999999;
for (k=i; k<=j-1; k++)
{
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+s[j]-s[i-1]);
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+s[j]-s[i-1]);
}
}
int ansmax=-99999,ansmin=99999;
for (i=1; i<=n; i++)
{
ansmax=max(ansmax,dpmax[i][i+n-1]);
ansmin=min(ansmin,dpmin[i][i+n-1]);
}
cout<<ansmin<<endl<<ansmax;
return 0;
}
复制代码
作者:
walk_alone
时间:
2018-7-29 18:49
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int v[501],sum[501];
int fmin[501][501];
int fmax[501][501];
int maximum=-999999,minimum=999999;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
v[i+n]=v[i];
}
for(int i=1;i<=n<<1;i++)
sum[i]=sum[i-1]+v[i];
for(int i=2*n-1;i>=1;i--)
for(int j=i+1;j<=i+n-1;j++)
{
fmin[i][j]=minimum;
for(int k=i;k<j;k++)
{
fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]);
fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]);
}
}
for(int i=1;i<=n;i++)
{
minimum=min(minimum,fmin[i][i+n-1]);
maximum=max(maximum,fmax[i][i+n-1]);
}
printf("%d\n%d",minimum,maximum);
return 0;
}
复制代码
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2