2017 icpc beijing J - Pangu and Stones

1698 단어 동적 기획

제목:


n더미 돌, l, r를 드립니다. 매번 구간 길이 [l, r]의 돌을 합병할 수 있습니다. 합병 대가는 돌의 수와
마지막에 한 무더기로 합병할 수 있냐고요. 0:합병 대가.

아이디어:


구간의 돌과 돌의 합을 계산하려면 먼저 접두사와 편리함을 구하고 뒤에 사용하도록 해라
dp[i][j][k]-구간[i,j]을 k더미로 합친 비용 dp 초기화 inf
구간 길이len에 1~n이 있으면 각len의 [i, j] 초기 dp[i][j][len]=0을 알 수 있다
각 렌 매거 k:2~len은 각 k에 대해 [i, j]를 두 부분 dp[i][j][k]=min(dp[i][j][k], dp[i][L][1]+dp[L+1][j][k][k-1])로 분해한다.
k의 구간 범위는 한 무더기로 통합할 수 있는 범주에 속한다. dp[i][j]=min(dp[i][j][1], dp[i][j][k]+sum[j]-sum[l-1]).
dp[1][n][1]이 답입니다.

AC 코드:

#include
#include
#include
#include
#include

using namespace std;
const int MaxN = 102;
const int inf = 0x3f3f3f3f;

int n,l,r;
int a[MaxN],sum[MaxN];
int dp[MaxN][MaxN][MaxN];

int main()
{
	while(~scanf("%d %d %d",&n,&l,&r)){
		for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
		for(int i = 1;i <= n; i++) sum[i] = sum[i - 1] + a[i];
		for(int i = 1;i <= n; i++){
			for(int j = 1;j <= n; j++){
				for(int k = 1;k <= n; k++){
					dp[i][j][k] = inf;
				}
			}
		}
		for(int len = 1;len <= n; len++){
			for(int i = 1;i + len - 1 <= n; i++){
				int j = i + len - 1;
				dp[i][j][len] = 0;
				for(int k = 2;k <= len; k++){
					for(int L = i;L <= j; L++){
						dp[i][j][k] = min(dp[i][j][k],dp[i][L][1] + dp[L + 1][j][k - 1]);
					}
					if(k <= r && k >= l) dp[i][j][1] = min(dp[i][j][1],dp[i][j][k] + sum[j] - sum[i - 1]);
				}
			}
		}
		if(dp[1][n][1] >= inf) printf("0
"); else printf("%d
",dp[1][n][1]); } }

좋은 웹페이지 즐겨찾기