JOI2008本選 問題4＠C++(-5)

典型的なDP。

mins[i][j][m-1]=0;で0

/*
TASKNO: 4
LANG: C++
NAME: Masaki Hara J
*/

#include <climits>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned int uint;

const int INIT_MAX=1000000000;

int main(int argc,char* argv[])
{
	FILE* in=fopen("input.txt","r");
	FILE* out=fopen("output.txt","w");
	int n,m;
	fscanf(in,"%d %d",&n,&m);
	vector<vector<pair<int,int> > > stones(n);
	vector<vector<vector<int> > > mins(n);//!!!
	for(int i=0;i<n;i++) {
		uint row_size;
		fscanf(in,"%d ",&row_size);
		stones[i].resize(row_size);
		mins[i].resize(row_size,vector<int>(m+1,INIT_MAX));
		for(uint j=0;j<row_size;j++) {
			fscanf(in,"%d %d",&stones[i][j].first,&stones[i][j].second);
			if(i==0) {
				mins[i][j][m]=0;
				continue;
			}
			for(uint k=0;k<stones[i-1].size();k++) {
				for(int l=0;l<=m;l++) {
					int curr_val=(stones[i][j].first-stones[i-1][k].first)*(stones[i][j].second+stones[i-1][k].second);
					if(curr_val<0)curr_val=-curr_val;
					mins[i][j][l]=min(mins[i][j][l],mins[i-1][k][l]+curr_val);
				}
			}
			if(i==1) {
				if(0<m) mins[i][j][m-1]=0;
				continue;
			}
			for(uint k=0;k<stones[i-2].size();k++) {
				for(int l=0;l<m;l++) {
					int curr_val=(stones[i][j].first-stones[i-2][k].first)*(stones[i][j].second+stones[i-2][k].second);
					if(curr_val<0)curr_val=-curr_val;
					mins[i][j][l]=min(mins[i][j][l],mins[i-2][k][l+1]+curr_val);
				}
			}
		}
	}
	int min_sum=INT_MAX;
	for(uint k=0;k<stones[n-1].size();k++) {
		for(int l=0;l<=m;l++) {
			min_sum=min(min_sum,mins[n-1][k][l]);
		}
	}
	for(uint k=0;k<stones[n-2].size();k++) {
		for(int l=0;l<m;l++) {
			min_sum=min(min_sum,mins[n-2][k][l+1]);
		}
	}
	fprintf(out,"%d\n",min_sum);
	fclose(out);
	fclose(in);
	return 0;
}