リングストーンマージ
13570 ワード
テーマは1つの円形の運動場の周囲にN山の石を置くことを説明して、今石を順番に1山に合併します.毎回隣接する2つの山だけを選んで新しい山に統合し、新しい石の山の数を、その合併の得点として記録することを規定しています.
N堆石を1堆に統合した最小得点と最大得点を計算するアルゴリズムを設計した.
入力フォーマットデータの1行目は正の整数Nであり、N堆石があることを示す.
2行目にはN個の整数があり、i番目の整数aiはi番目の堆石の個数を表す.
出力フォーマット出力は2行で,1行目が最小得点,2行目が最大得点である.
入力
しゅつりょく
リングをつけたらどうしますか.断環は鎖である:長さnの鎖をコピーして後ろに接続し、環の場合、長さ2 nの鎖のうち任意の連続した長さnの鎖である.コードは次のとおりです.
N堆石を1堆に統合した最小得点と最大得点を計算するアルゴリズムを設計した.
入力フォーマットデータの1行目は正の整数Nであり、N堆石があることを示す.
2行目にはN個の整数があり、i番目の整数aiはi番目の堆石の個数を表す.
出力フォーマット出力は2行で,1行目が最小得点,2行目が最大得点である.
入力
4
4 5 9 4
しゅつりょく
43
54
リングをつけたらどうしますか.断環は鎖である:長さnの鎖をコピーして後ろに接続し、環の場合、長さ2 nの鎖のうち任意の連続した長さnの鎖である.コードは次のとおりです.
#include
using namespace std;
int f[210][210];
int ff[210][210];
int v[210][210];
int a[220];
int n;
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*2;i++)
{
for(int j=1;j<=n*2;j++)
{
if(i!=j)
f[i][j]=10000000;
}
}
for(int i=1;i<=n*2;i++)
{
for(int j=i;j<=n*2;j++)
{
for(int k=i;k<=j;k++)
{
v[i][j]+=a[k];
}
}
}
for(int len=1;len<=n;len++)
for(int l=1,r=l+len;l<n*2&&r<n*2;l++,r=l+len)
{
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+v[l][r]);
ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+v[l][r]);
}
}
int ans1=10000000,ans2=0;
for(int i=1;i<=n;i++) ans1=min(ans1,f[i][i+n-1]);
for(int i=1;i<=n;i++) ans2=max(ans2,ff[i][i+n-1]);
cout <<ans1<<endl;
cout <<ans2;
return 0;
}