左右をもつタイプの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．
