wikioi 1048 돌멩이 병합
6644 단어 IO
i-j의 최소 합병 대가를 나타낸다.
1 #include <iostream>
2 #include <string.h>
3 #include <stdio.h>
4
5 using namespace std;
6 const int INF = 1 << 30;
7 const int N = 205;
8
9 int dp[N][N];
10 int sum[N];
11 int a[N];
12
13 int getMinval(int a[],int n)
14 {
15 for(int i=0;i<n;i++)
16 dp[i][i] = 0;
17 for(int v=1;v<n;v++)
18 {
19 for(int i=0;i<n-v;i++)
20 {
21 int j = i + v;
22 dp[i][j] = INF;
23 int tmp = sum[j] - (i > 0 ? sum[i-1]:0);
24 for(int k=i;k<j;k++)
25 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + tmp);
26 }
27 }
28 return dp[0][n-1];
29 }
30
31 int main()
32 {
33 int n;
34 while(scanf("%d",&n)!=EOF)
35 {
36 for(int i=0;i<n;i++)
37 scanf("%d",&a[i]);
38 sum[0] = a[0];
39 for(int i=1;i<n;i++)
40 sum[i] = sum[i-1] + a[i];
41 printf("%d
",getMinval(a,n));
42 }
43 return 0;
44 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 입출력 I/O스트림(stream) 자바에서 입출력을 수행하려면 두 대상을 연결하고 데이터를 전송할 수 있는 무언가가 필요한데 이것을 스트림(stream)이라고 정의했다. 스트림은 단방향 통신만 가능하기 때문에 하나의 스트림으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.