구간 DP 요약
20457 단어 구간DP
구간DP는 주로 하나의 큰 구간을 몇 개의 단지 간으로 나누어 먼저 단지 간의 최우수치를 구한 다음에 합쳐서 큰 구간의 최우수치를 구한다.
구간 DP의 가장 관건적인 것은 최우수 서브구조와 후효성을 만족시키는 것이다!!!
// DP
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++） // 1
dp[i][i] = 0;
for (int len = 2; len <= n; len++) //
{
for (int i = 1, j = len; j <= n; i++, j++) // [i,j]
{
//DP
}
}우리는 dp를 상태 이동 방정식 수조로 규정하고 a는 데이터 수조(하표는 1부터),sum는 데이터 접두사와 수조로 a[]={1,2,3,4},sum[]={1,3,6,10}을 가설한다.
첫 번째 모델
돌병합
한 직선에 N더미의 돌이 있는데, 지금은 모든 돌을 한 무더기로 합쳐야 한다. 매번 서로 인접한 두 무더기만 합칠 수 있고, 합치는 비용은 새로 합성한 돌무더기의 수량으로 최소한의 비용을 요구한다.
1무더기, 비용은 02무더기, 비용은sum[2]3무더기, 비용은min(a[1]+a[2], a[2]+a[3])+sum[3]이다. 만약에 우리가 n무더기가 있다면 합병의 마지막 조작은 반드시 두 무더기에서 한 무더기로 합병한다.
첫 번째 모델은 큰 구간을 임의의 위치에서 두 개의 단지 사이로 나누는 것이다
규정 dp[i][j]가 제i더미에서 제j더미로 합병하기 위한 최소 비용 DP 방정식은 dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[j]-sum[i-1](i<=k
// O(n^3) O(n^2)
//http://blog.csdn.net/find_my_dream/article/details/4931222
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[i][i] = 0;
for (int len = 2; len <= n; len++)
{
for (int i = 1, j = len; j <= n; i++, j++)
{
for (int k = i; k < j; k++)
{
if(dp[i][j] > dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];
}
}
}
printf("%d
", dp[1][n]); 두 번째 모델
괄호 일치poj2955
괄호로 구성된 문자열에 최대 몇 개의 괄호([)]와 같은 문자열의 일치도는 2이지만 ()[], [()]와 같은 문자열의 일치도는 4이다. 즉, 괄호는 구분 작용을 한다.
길이 1의 직렬 일치도 0 길이 2의 직렬 일치도 0 또는 2
dp[i][j]가 i에서 j까지의 문자의 최대 일치도 길이를 n으로 합치기 위해 a[i]와 a[j]가 일치하는지 검사할 수 있습니다. dp[i][j]=dp[i+1][j-1]+2가 일치하지 않으면 우리는 첫 번째 모델에 따라 처리하고 임의의 위치에서 두 구간으로 나눌 수 있습니다.
while (gets(a+1))
{
if (a[1] == 'e') break;
memset(dp, 0, sizeof(dp));
int n = strlen(a+1);
for (int len = 2; len <= n; len++)
{
for(int i = 1, j = len; j <= n; i++, j++)
{
if((a[i]=='('&&a[j]==')') || (a[i]=='['&&a[j]==']'))
dp[i][j] = dp[i+1][j-1] + 2;
for (int k = i; k < j; k++)
if(dp[i][j] < dp[i][k] + dp[k+1][j])
dp[i][j] = dp[i][k] + dp[k+1][j];
}
}
printf("%d
",dp[1][n]);
}물론 이렇게 해서 두 번째 모델이라고 할 수는 없다
우리는 [i, j] 구간의 문자를 [i+1, j]가 앞에 문자를 붙이거나 [i, j-1]가 뒤에 문자를 붙이는 것으로 간주할 수 있다
여기서 우리는 [i, j]가 [i+1, j]에서 앞에 문자를 추가하는 상황만 고려한다. 만약에 a[i+1]에서 a[j]까지 a[i]와 일치하는 것이 없다면 dp[i][j]=dp[i+1][j]가 a[k]와 a[i]가 일치한다면 dp[k<=j]=max(dp[i][j], dp[i+1][k-1]+dp[k+1][j]+2).예를 들어: [xxxx] yyyyy는 괄호를 통해 두 개의 자열로 나뉜다
두 번째 모델은 일치하는 정보에 따라 구간을 [i+1,k-1]과 [k+1,j]로 나누는 것이다.
//
while (gets(a+1))
{
if(a[1] == 'e') break;
memset(dp, 0, sizeof(dp));
int n = strlen(a+1);
for (int len = 2; len <= n; len++)
{
for(int i = 1, j = len; j <= n; i++, j++)
{
dp[i][j] = dp[i+1][j];
for (int k = i; k <= j; k++)
if((a[i]=='('&&a[k]==')') || (a[i]=='['&&a[k]==']'))
dp[i][j] = max(dp[i][j], dp[i+1][k-1] + dp[k+1][j] + 2);
}
}
printf("%d
",dp[1][n]);
}두 문제 보고 이런 모형을 느껴보세요^-^
You Are the One HDU 4283
Halloween Costumes Light OJ-1422는 이와 별 차이가 없다. 한 무리의 깡패들이 한 줄로 서 있다. 첫 번째 K의 깡패 값은 a[i]*(k-1)이다. 작은 검은 집(창고)을 통해 순서를 조정할 수 있지만 먼저 방에 들어간 마지막에야 나올 수 있다. 깡패 값과 가장 작은 값을 구한다.사고방식: 우선, 우리는 창고에 순서가 있다는 것을 안다. 예를 들어 1, 2, 3이 모두 창고에 들어가면 반드시 3, 2, 1이 된다.dp[i][j]를 i개인부터 j개인까지 등장하는 최소 찌질치로 규정한다.만약에 i개인이 k번째로 출전(1<=k<=j-i+1)한다면 [i+1, i+k-1] 구간의 사람들은 반드시 i가 등장하기 전에 모두 출전해야 한다. 이때 마침 창고가 비어 있다. 앞의 k개인이 모두 출전한 다음에 i의 출전 순서로 구간을 구분할 수 있다??DP 방정식: dp[i][j]=min(dp[i][j], dp[i+1][i+k-1]+a[i]*(k-1)+dp[i+k][j]+(sum[j]-sum[i+k-1])*k)
memset(dp, 0, sizeof(dp)); // dp[j+1][j] ， 0
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
dp[i][j] = INF;
for (int len = 2; len <= n; len++)
{
for (int i = 1, j = len; j <= n; i++, j++)
{
for (int k = 1; k <= j-i+1; k++)//k [i,j]，
dp[i][j] = min(dp[i][j], dp[i+1][i+k-1] + a[i]*(k-1) + dp[i+k][j] + (sum[j]-sum[i+k-1])*k);
}
}String painter HDU - 2476
이 문제는 먼저 구간 dp로 미리 처리해야 한다. 공백을 직렬 t로 바꾸는 최소 비용을 계산한 다음에 직렬 s에서 직렬 t로 가는 최소 비용을 계산한다. 코드를 보자.
#include
", a[n]);
}
return 0;
}세 번째 모델
이런 유형은 비교적 간단하기 때문에 매거구간 k∈[i,j]을 필요로 하지 않는다. 이런 유형은 좌우 경계와만 관련이 있다.
Cheapest Palindrome POJ 3280
제목: n개의 문자는 길이가 m인 문자열로 구성되어 있으며, 문자를 삭제하는 비용을 주고, 문자열의 임의의 위치에서 문자를 삭제할 수 있으며, 문자열을 회문열의 최소 비용으로 수정할 수 있습니다.dp[i][j]를 [i, j] 구간을 회문열로 바꾸는 최소 비용으로 회문열 [i+1, j]이 앞에 문자=>앞의 삭제 또는 뒤의 증가[i, j-1]를 뒤에 문자=>앞의 증가 또는 뒤의 삭제 등 네 가지 상황으로 볼 수 있다. a[i]=a[j]가 있을 때 dp[i+1][j-1]을 추가하면 된다.
#include
", dp[1][m]);
return 0;
}Tian Ji – The Horse Racing HDU 1052
제목: 전기경마에서 한 경기를 이기면 200, 한 경기를 지고 200을 진다. 마지막에 가장 많이 이기면 얼마(or가 가장 적게 지는) 사고방식을 묻는다. 제왕이 가장 강한 말부터 시작한다고 가정하면 전기가 가장 강한 말이 제왕이 가장 강한 말을 이길 수 있다면 가장 강한 말로 이길 수 없고 가장 약한 말을 이길 수 있다.욕심 같지 않아요?그러나 가장 강한 타이브레이크를 처리하는 것은 비교적 번거롭기 때문에 타이브레이크를 선택하거나 지는 것을 선택할 수 있다.
예를 들어 전기의 말 속도는 2, 3으로 제왕 1, 3, 이렇게 속도는 3으로 비겼고 속도는 2로 이겼다.전기의 말 속도는 1, 2, 3, 4로 제왕의 말 속도는 1, 2, 3, 4로 스피드 1이 4에 졌고 다른 3승은 3승이었다.
하지만 매번 가장 강한 선수를 보내든지, 가장 약한 선수를 보내든지 분석할 수 있다.여기서는 DP 방법만 다룹니다.규정 dp[i][j]는 전기 제i에서 제j까지의 말과 제왕의 느린 j-i+1마리의 말의 승전보다 패배 수치를 감소시킨다
우리는 계속해서 이 예를 보았다. 전기의 말 속도 1, 2, 3, 4제왕의 말 속도 1, 2, 3, 4dp[1][3]는 전기의 속도 1, 2, 3의 말과 제왕의 속도 1, 2, 3의 말 비dp[2][4]는 전기의 속도 2, 3, 4의 말과 제왕의 속도 1, 2, 3의 말 비이다.
dp[1][4]는 전기의 속도가 1, 2, 3, 4인 말과 제왕의 속도가 1, 2, 3, 4인 말은 우리가 그를 [1,3]에 속도 4를 더한 말로 볼 수 있다. [2,4]에 속도 1을 더한 말은 제왕이 모두 속도 4를 더한 말이다.이때 두 가지 선택이 있다.가장 강한 말(속도 4)과 제왕의 강한 말을 겨루다.가장 느린 말(속도 1)과 제왕의 강마를
#include
", dp[1][n] * 200);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ2955: Brackets(구간 DP)제목: 괄호 서열을 하나 드릴게요. 괄호는 두 가지(,)와 [,](), [], (), (), (), [], ()] [()] 이 괄호가 모두 일치하는 (,),(,(,)), ([(] 이런 것은 완전히 일치하지 않는 거예...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
