hit 2952//돌을 병합한 평행 사각형 부등식 해법
1611 단어 ACM_동적 기획
이어서 초기화에 주의해 주세요.
#include
#include
const int MAXN = 1010 * 2;
const int inf = 1 << 29;
int a[MAXN];
int sum[MAXN];
int dp[MAXN][MAXN], s[MAXN][MAXN];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i + n] = a[i];
}
sum[0] = 0;
for(int i = 1; i <= 2 * n; i++)
{
sum[i] = sum[i-1] + a[i];
}
for(int i = 1; i <= 2 * n; i++)
{
s[i][0] = i;
dp[i][0] = 0;
}
for(int k = 1; k < n; k++)
{
s[2*n-k+1][k] = 2 * n - 1;
for(int i = 2 * n - k; i >= 0; i--)
{
dp[i][i+k] = inf;
for(int j = s[i][k-1]; j <= s[i+1][k]; j++)
{
int temp = dp[i][j] + dp[j+1][i+k] + sum[i+k] - sum[i-1];
//printf("i=%d j=%d i+k=%d %d
",i,j,i+k,temp);
if(temp < dp[i][i+k])
{
dp[i][i+k] = temp;
s[i][k] = j;
}
}
//printf("dp[%d][%d]=%d
",i,i+k,dp[i][i+k]);
}
}
int ans = inf;
for(int i = 1; i <= n; i++)
if(dp[i][i+n-1] < ans) ans = dp[i][i+n-1];
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 1025_A Spy in the Metro[제의] (소자서) 한 사람이 플랫폼 1에서 출발하면 차를 타려면 시간 T에 플랫폼 n에 도착해야 한다. 플랫폼에서 차를 기다리는 시간이 가장 짧기 때문에 그녀는 두 방향의 열차를 타고 버스가 정차할 때 갈아타야 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.