[동적 기획 연습문제] 학생 기숙사(충칭1중고 2018급 정보학 경연 테스트 10) 문제풀이 보고서

[문제 설명]
  
새로운 학생 기숙사가 개방되었는데, 그것은 M동 건물로 구성되어 있으며, 표호는 1에서 M이다.처음에는 학생 기숙사가 모두 비어 있었고 곧 N 명의 학생이 이사 들어갔다.마침 매일 하나씩 이사 들어갔어요. 
매번 새 동창이 기숙사로 이사할 때마다 그 건물은 대형 파티를 열 것이다.파티의 소음은 이 건물의 학생 수와 같다.기숙사 관리원은 소음을 좋아하지 않기 때문에 비정기적으로 어떤 건물을 비운다.비우는 방법은 이 건물의 학생들을 모두 다른 학생 기숙사(이 M동 기숙사 이외의 곳)로 몰아내는 것이다.하지만 관리자는 최대 K회까지만 비울 수 있습니다.n일 소음의 합계의 최소치를 구하세요. 
 
    
[형식 입력]
  
첫 번째 줄의 세 정수 n, m, k.
다음은 n줄이 있고 줄마다 정수 비(1<=비<=m)가 있다. 이는 i일째 되는 날 한 학생이 비동 기숙사로 이사했다는 뜻이다.
[출력 형식]
   
n일 소음의 합을 나타내는 정수
[샘플 입력]
   
5 1 2
1
1
1
1
1 
 
    
[샘플 내보내기]
   
7 
 
    
[예제 해석]
   
예제 1 설명: 첫날과 3일 후에 비우기 작업을 실행합니다.이렇게 매일의 소음은 1,2,1,2이기 때문에 소음의 합은 7이다. 
 
    
[데이터 범위]
   
1<=n<=1000000,1<=m<=100,1<=k<=500
 
    
【출처】
  
http://www.cqoi.net:2012/problem.php?id=2916
 
문제 풀이 사고방식(오해): 이 문제를 받았을 때 가장 먼저 떠오르는 것은 동적 기획이다. 그러나 상태 함수를 설계할 때 상태 함수가 전 i일과 관련이 있다고 생각하고 f(i, j)를 설정하면 전 i일에 j회에서 얻은 소음과 최소치를 비웠다는 것을 나타낸다. 그래서 유도 상태 이동 방정식에 끼었다.
문제풀이 방향(정해): 문제의 뜻에 따라 소음과 최소값을 요구하기 때문에 자연히 동적 계획 알고리즘을 사용해야 한다. 데이터 범위의 제시에 따라 이전에 생각한 대로 상태 함수를 설정하면 메모리를 초과할 수 있기 때문에 f(i, j)를 설정하면 전 i동 기숙사가 j번에 얻은 소음과 최소값을 비울 수 있다. i동 기숙사를 분석할 때 이 기숙사는 0회, 1회, 최대 j회, 최대 j회까지 비울 수 있다.그래서 f(i, j)=min{f(i-1, j-k)|0<=k<=j}+g[i][k], g[i][k]는 제i동 기숙사에서 k회 청소한 소음과 최소치를 나타낸다. 경계는 f(0, j)=0이다.
현재의 주요 문제는 어떻게 g[i][k]를 계산합니까?i동 기숙사에서 k회를 비운 후 얻은 소음과 최소화를 위해 i동 기숙사에 들어간 학생 수를 평균적으로 k+1부(k부가 아닌 주의)로 나누어야 하기 때문에 이때 구한 소음과 즉 최소로 소음을 계산할 때 순환적으로 계산하지 않아도 된다. 이것이 바로 등차수열구화의 문제임이 분명하다.먼저 학생 수를 k+1부로 나눈 후 값 t(즉 기숙사 비우기 전의 인원수)와 학생 수를 k+1등분으로 나눈 후 남은 인원수tt(남은 사람은 매번 비우기 전의 기숙사에 순서대로 나눈다)를 계산하면 g[i][k]=(1+2+...+t)*(k+1)+(t+1)*tt.

#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000005;
const long long inf=1000000000010ll;
typedef long long LL;
int N,M,K;
int b[maxn],a[105];
LL g[105][505];  //g[i][k]   i     k           
/*
f(i,j)   i     j           
f(i,j)=min{f(i-1,j-k)+g[i][k] | 0<=k<=j} 
  ：f(0,j)=0 
*/
LL d[105][505];
int read_()  //    ，    
{
	char s;
	s=getchar();
	while(s'9')  s=getchar();
	int x=0;
	while(s>='0' && s<='9')  
	{
		x=x*10+s-'0';
		s=getchar();
	}
	return x;
}
void solve()
{
	for(int i=0;i<=M;i++)
	for(int j=0;j<=K;j++)
	d[i][j]=inf;
	for(int j=0;j<=K;j++)
	d[0][j]=0;
	for(int i=1;i<=M;i++)
	for(int j=0;j<=K;j++)
	{
		LL t=inf;
		for(int k=0;k<=j;k++)
		t=min(t,d[i-1][j-k]+g[i][k]);
		d[i][j]=t;
	}
	cout<