nyoj737 돌멩이 합병【구간dp】
논문 문제 마지막에 수조를 구하고 [1,n][2,n+1]을 찾아야 하는데......[n, n+n+1]의 최고치, 이 문제는 첫 번째 문제만 출력하면 됩니다.
이 문제는 특별히 나를 괴롭히는 점이 하나 있다. 구간마다 두 단락으로 나뉘는데, 뒷부분의 값이 아직 두루 퍼지지 않았는데, 어떡하지?그래서 1층 순환은 구간의 길이이고 2층 순환은 구간의 시작이며 3층 순환은 구간의 중점이다.보아하니 dp의 관건도 상태 이동 방정식을 쓰는 것만은 아닌 것 같다.
/******************
nyoj737
2016.2.18
732 868 C/C++ 02-18 15:47:11
******************/
#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;
int f[403][403],n,num[403],t[403];
void init()
{
t[0]=0;
for(int i=1;i<=2*n-1;i++)t[i]=t[i-1]+num[i];
}
void cal()
{
memset(f,0x3f3f3f3f,sizeof(f));
for(int i=1;i<=2*n-1;i++) f[i][i]=0;
for(int k=1;k<n;k++)//length
for(int i=1;i<=n;i++)//start
for(int j=i;j<i+k;j++)//mid
{
f[i][i+k]=min(f[i][i+k],f[i][j]+f[j+1][i+k]+t[i+k]-t[i-1]);
}
//for(int i=1;i<=n;i++)for(int j=i+1;j<=i+n-1;j++) printf("i=%d,j=%d,f=%4d\t\t",i,j,f[i][j]);
}
int main()
{
//freopen("cin.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
for(int i=n+1;i<=2*n;i++) num[i]=num[i-n];
// for(int i=1;i<=2*n-1;i++) printf("i=%d,num=%d
",i,num[i]);
init();
cal();
int maxn=0x3f3f3f3f;
// for(int i=1;i<=n;i++) printf("i=%d,j=%d,f=%d
",i,i+n-1,f[i][i+n-1]);
printf("%d
",f[1][n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
