ACM-ICPC Asia Beijing Regional Contest 2017-J-Pangu and Stones-구간 dp-합병석자 진급
ACM-ICPC Asia Beijing Regional Contest 2017-J-Pangu and Stones-구간 dp-합병석자 진급
4
Description
In Chinese mythology, Pangu is the first living being and the creator of the sky and
the earth. He woke up from an egg and split the egg into two parts: the sky and the earth.
At the beginning, there was no mountain on the earth, only stones all over the land.
There were N piles of stones, numbered from 1 to N. Pangu wanted to merge all of them
into one pile to build a great mountain. If the sum of stones of some piles was S, Pangu
would need S seconds to pile them into one pile, and there would be S stones in the new
pile.
Unfortunately, every time Pangu could only merge successive piles into one pile. And
the number of piles he merged shouldn't be less than L or greater than R.
Pangu wanted to finish this as soon as possible.
Can you help him? If there was no solution, you should answer '0'.
Input
There are multiple test cases.
The first line of each case contains three integers N,L,R as above mentioned
(2<=N<=100,2<=L<=R<=N).
The second line of each case contains N integers a1,a2 …aN (1<= ai <=1000,i= 1…N ),
indicating the number of stones of pile 1, pile 2 …pile N.
The number of test cases is less than 110 and there are at most 5 test cases in which N
>= 50.
Output
For each test case, you should output the minimum time(in seconds) Pangu had to take . If
it was impossible for Pangu to do his job, you should output 0.
Examples
Input
3 2 2
1 2 3
3 2 3
1 2 3
4 3 3
1 2 3 4
Output
9
6
0
Problem Description
。
, X ,L<=x<=R, 。 。
Solution
dp
[L,R] , dp , [L,R] 。 code。
Code
/*
* @Author: Simon
* @Date: 2018-08-20 13:30:43
* @Last Modified by: Simon
* @Last Modified time: 2018-08-20 14:43:25
*/
#include
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
#define maxn 105
int a[maxn];
int dp[maxn][maxn][maxn];//dp[i][j][k], i~j k
Int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,l,r;
while(cin>>n>>l>>r)
{
memset(dp,INF,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i][i][1]=0;
cin>>a[i];
a[i]+=a[i-1];
}
for(int x=l-1;x//
{
for(int i=1;i+x<=n;i++)
{
int j=x+i;
dp[i][j][x+1]=0;// x , x 0
dp[i][j][1]=a[j]-a[i-1];//
}
}
for(int x=1;x//
{
for(int i=1;i+x<=n;i++)
{
int j=x+i;
for(int k=i;kfor(int c=2;c<=x+1;c++)//
{
dp[i][j][c]=min(dp[i][j][c],dp[i][k][c-1]+dp[k+1][j][1]);
}
}
for(int c=l;c<=r;c++)//
dp[i][j][1]=min(dp[i][j][1],dp[i][j][c]+a[j]-a[i-1]);
}
}
if(dp[1][n][1]>=INF)
{
cout<<0<else cout<1][n][1]<cin.get(),cin.get();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.