読者です 読者をやめる 読者になる 読者になる

PKU 1991 Turning in Homework

左右をもつタイプのDP。
結構大変ですが、なんとかはなります。

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> p[1000];
int t[1001];
int dp[1001][1001][2];
int ABS(int a){return max(a,-a);}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d%d",&p[i].first,&p[i].second);
	}
	std::sort(p,p+a);
	for(int i=0;i<=a;i++)
		for(int j=0;j<=a;j++)
			dp[i][j][0]=dp[i][j][1]=999999999;
	for(int i=0;i<a;i++)t[i+1]=p[i].first;
	dp[0][0][0]=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(i+j>=a)continue;
		//	printf("%d %d 0: %d\n",i,j,dp[i][j][0]);
		//	printf("%d %d 1: %d\n",i,j,dp[i][j][1]);
			dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][0]+t[a-j]-t[i]);
			dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][1]+t[a-j+1]-t[a-j]);
			if(dp[i][j+1][1]<p[a-j-1].second)dp[i][j+1][1]=p[a-j-1].second;
			dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][0]+t[i+1]-t[i]);
			dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][1]+t[a-j+1]-t[i+1]);
			if(dp[i+1][j][0]<p[i].second)dp[i+1][j][0]=p[i].second;
		}
	}
	int ret=999999999;
	for(int i=0;i<=a;i++){
		ret=min(ret,dp[i][a-i][0]+ABS(c-t[i]));
		ret=min(ret,dp[i][a-i][1]+ABS(c-t[i+1]));
	}
	printf("%d\n",ret);
}

USACO残り12.