zoj3469 区间dp好题

/* 按坐标排序 以餐厅为起点向两边扩展区间 dp[i][j][0]表示送完区间[i,j]的饭后停留在左边的代价 dp[i][j][1]表示送完区间[i,j]的饭后停留在右边的代价 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct A{int x,v;}p[1050]; int cmp(A a,A b){return a.x<b.x;} int sum[1050],dp[1050][1050][2],n,v,x;//代价，坐标 int main(){ while(cin>>n>>v>>x){ for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].v); p[n+1].x=x,p[n+1].v=0; sort(p+1,p+n+2,cmp); int pos;//找餐厅 for(int i=1;i<=n+1;i++) if(p[i].x==x){pos=i;break;} memset(sum,0,sizeof sum); for(int i=1;i<=n+1;i++) sum[i]=sum[i-1]+p[i].v; memset(dp,0x3f,sizeof dp); dp[pos][pos][0]=dp[pos][pos][1]=0; for(int i=pos;i>=1;i--) for(int j=pos;j<=n+1;j++){ if(i==j)continue; int delay=sum[i-1]+sum[n+1]-sum[j]; dp[i][j][0]=min(dp[i+1][j][0]+(p[i+1].x-p[i].x)*(delay+p[i].v),//从i+1走到i dp[i+1][j][1]+(p[j].x-p[i].x)*(delay+p[i].v));//从j走到i dp[i][j][1]=min(dp[i][j-1][0]+(p[j].x-p[i].x)*(delay+p[j].v),//从i走到j dp[i][j-1][1]+(p[j].x-p[j-1].x)*(delay+p[j].v));//从j-1走到j } printf("%d\n",min(dp[1][n+1][0],dp[1][n+1][1])*v); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10317291.html