[NOI1995] 돌멩이 합병 & [NOIP2006] 에너지 목걸이 문제풀이
구간 dp 고전 문제
분명히 이 문제는 과일 합병 그 문제와 다르다
우리는 dp[i][j]를 설정하여 i에서 j까지 이 구역 내의 최대/최소 가치를 나타낸다
그리고 분명히 우리는 i에서 j까지 단점 k를 선택하고 (max를 예로 들면)
1 dp[i][j] = std::max (dp[i][j] , dp[i][k] + dp[k + 1][j] + sum(i, j));
그중sum(i,j)는 i에서 j까지의 돌의 총수(접두사와 가능)
그럼 매거를 어떻게 하죠?
1 for(int i = 1; i <= n; i++){
2 for(int j = 1; j <= n; j++){
3 for(int k = i; k < j; k++){
4 dp[i][j] = std::max (dp[i][j] , dp[i][k] + dp[k + 1][j] + sum(i, j));
5 }
6 }
7 }이렇게?Too Simple!
우리는 우리가 필요로 할 수 있는 dp[k+1][j]가 이 구간의 답이 아니라 초기값이라는 것을 쉽게 발견할 수 있다(k+1!=j, 같으면 원래 초기값이어야 한다)
그럼 우리 생각을 바꿔서 (j-i)라는 차액을 매거하자.
그럼 이동에 필요한 상태가 다 있다는 보장이 되잖아요
그 밖에 이 문제는 고리이기 때문에 우리는 고리를 깨뜨려 체인으로 하고 구체적인 방법은 코드를 보아야 한다
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define APART puts("----------------------")
8 #define debug 1
9 #define FILETEST 1
10 #define inf 310
11 #define ll long long
12 #define ha 998244353
13 #define INF 0x7fffffff
14 #define INF_T 9223372036854775807
15 #define DEBUG printf("%s %d
",__FUNCTION__,__LINE__)
16
17 namespace chino{
18
19 inline void setting(){
20 #if FILETEST
21 freopen("_test.in", "r", stdin);
22 freopen("_test.me.out", "w", stdout);
23 #endif
24 return;
25 }
26
27 inline int read(){
28 char c = getchar(), up = c; int num = 0;
29 for(; c < '0' || c > '9'; up = c, c = getchar());
30 for(; c >= '0' && c <= '9'; num = (num << 3) + (num << 1) + (c ^ '0'), c = getchar());
31 return up == '-' ? -num : num;
32 }
33
34 int n;
35 int num[inf];
36 int sum[inf];
37 int dpmin[inf][inf];
38 int dpmax[inf][inf];
39
40 inline int main(){
41 n = read();
42 for(int i = 1; i <= n; i++)
43 num[i + n] = num[i] = read();
44 for(int i = 1; i <= (n << 1); i++)
45 sum[i] = sum[i - 1] + num[i];
46 for(int c = 1; c < n; c++){
47 for(int i = 1, j = 1 + c; i < (n << 1) && j < (n << 1); i++, j = i + c){
48 dpmin[i][j] = INF >> 1;
49 for(int k = i; k < j; k++){
50 dpmin[i][j] = std::min (dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + sum[j] - sum[i - 1]);
51 dpmax[i][j] = std::max (dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j] + sum[j] - sum[i - 1]);
52 }
53 }
54 }
55 int ansmin = INF, ansmax = -INF;
56 for(int i = 1; i <= n; i++){
57 ansmin = std::min (ansmin, dpmin[i][i + n - 1]);
58 ansmax = std::max (ansmax, dpmax[i][i + n - 1]);
59 }
60 printf("%d
%d
", ansmin, ansmax);
61 return 0;
62 }
63
64 }//namespace chino
65
66 int main(){return chino::main();} 별문제
[NOIP2006] 에너지 목걸이
또 하나의 구간 dp 고전 문제
돌멩이랑 합치면 좀 비슷해요.
문제를 보자마자 네이버에서 돌을 합쳐서 고쳐서 10pts로 굴렀어요.
방법은 모든 구간(i, j)을 매거진 다음에 단점 k를 매거진 것이다. 구간(i, j)의 답은 (i, k)와 (k+1, j)에서 옮겨진다.
10pts:
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define APART puts("----------------------")
8 #define debug 1
9 #define FILETEST 1
10 #define inf 1010
11 #define ll long long
12 #define ha 998244353
13 #define INF 0x7fffffff
14 #define INF_T 9223372036854775807
15 #define DEBUG printf("%s %d
",__FUNCTION__,__LINE__)
16
17 namespace chino{
18
19 inline void setting(){
20 #if FILETEST
21 freopen("_test.in", "r", stdin);
22 freopen("_test.me.out", "w", stdout);
23 #endif
24 return;
25 }
26
27 inline int read(){
28 char c = getchar(), up = c; int num = 0;
29 for(; c < '0' || c > '9'; up = c, c = getchar());
30 for(; c >= '0' && c <= '9'; num = (num << 3) + (num << 1) + (c ^ '0'), c = getchar());
31 return up == '-' ? -num : num;
32 }
33
34 int n;
35 int ans;
36 int a[inf];
37 int dp[inf][inf];
38
39 inline int main(){
40 n = read();
41 for(int i = 1; i <= n; i++)
42 a[i + n] = a[i] = read();
43 n <<= 1;
44 for(int i = 1; i <= n; i++){
45 for(int j = i + 1; j <= n && j - i < (n >> 1); j++){
46 if(j - i == 1)
47 dp[i][j] = a[i] * a[j] * a[j + 1];
48 for(int k = i + 1; k < j; k++)
49 dp[i][j] = std::max (dp[i][j] , dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);
50 ans = std::max (ans, dp[i][j]);
51 }
52 }
53 printf("%d
", ans);
54 return 0;
55 }
56
57 }//namespace chino
58
59 int main(){return chino::main();} 오류의 원인도 간단하다. 하나는 i, j, k의 범위를 잘 제어하지 못했고 가장 중요한 것은 이동할 때 dp[k+1][j]가 이동한 적이 없다는 것이다.
그럼 어떻게 피해요?
우리의 이 방법은 왼쪽 단점 i를 취한 다음에 오른쪽 단점 j를 찾고 단점 k를 찾는 것이다
그러면 우리는 반대로 먼저 오른쪽 단점 i를 매거한 다음에 왼쪽 단점 j를 매거한 다음에 단점 k를 찾는다
이렇게 하면 매번 옮길 때마다 문제가 없다는 것을 보증한다
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define APART puts("----------------------")
8 #define debug 1
9 #define FILETEST 1
10 #define inf 1010
11 #define ll long long
12 #define ha 998244353
13 #define INF 0x7fffffff
14 #define INF_T 9223372036854775807
15 #define DEBUG printf("%s %d
",__FUNCTION__,__LINE__)
16
17 namespace chino{
18
19 inline void setting(){
20 #if FILETEST
21 freopen("_test.in", "r", stdin);
22 freopen("_test.me.out", "w", stdout);
23 #endif
24 return;
25 }
26
27 inline int read(){
28 char c = getchar(), up = c; int num = 0;
29 for(; c < '0' || c > '9'; up = c, c = getchar());
30 for(; c >= '0' && c <= '9'; num = (num << 3) + (num << 1) + (c ^ '0'), c = getchar());
31 return up == '-' ? -num : num;
32 }
33
34 int n;
35 int ans;
36 int a[inf];
37 int dp[inf][inf];
38
39 inline bool check(int i, int j){
40 return (i - j) < n && j;
41 }
42
43 inline int main(){
44 n = read();
45 for(int i = 1; i <= n; i++)
46 a[i + n] = a[i] = read();
47 int nn = n << 1;
48 for(int i = 2; i < nn; i++){
49 for(int j = i - 1; check(i, j); j--){
50 for(int k = j; k < i; k++)
51 dp[i][j] = std::max (dp[i][j], dp[i][k + 1] + dp[k][j] + a[i + 1] * a[k + 1] * a[j]);
52 ans = std::max (ans, dp[i][j]);
53 }
54 }
55 printf("%d
", ans);
56 return 0;
57 }
58
59 }//namespace chino
60
61 int main(){return chino::main();} 전재 대상:https://www.cnblogs.com/chiarochinoful/p/problem-noi-1995-shizihebing.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
