假設此時已經安慰好了第i個MM和第j個MM及其之間的所有MM。如果此時站在第i個MM所在的位置，用d[i,j,0]表示之后需要消耗的最小RP；如果此時站在第j個MM所在的位置，用d[i,j,1]表示在此之后需要消耗的最小RP。
那么就有：
d[i,j,0]=min{ d[i-1,j,0]+abs(r[i]-r[i-1])*(s[n]-s[j]+s[i-1]),
d[i,j+1,1]+abs(r[i]-r[j+1])*(s[n]-s[j]+s[i-1]) }；
d[i,j,1]時的情況可以類似寫出。
其中r[i]表示第i個MM所在的位置，s[i]表示前i個MM的w[i]的和。
以下是我的代碼：
#include<iostream>
#include<string.h>
#include<stdlib.h>
#define maxn 1007
#define inf 2000000000
using namespace std;
long min(long a,long b){return (a<b?a:b);}
long n,v,r[maxn],w[maxn],s[maxn];
long d[maxn][maxn][2];
long dp(long i,long j,long k)
{
if(d[i][j][k]!=-1) return d[i][j][k];
d[i][j][k]=inf;
if(k==0)
{
if(i-1>=0)
d[i][j][k]=min(d[i][j][k],dp(i-1,j,0)+abs(r[i]-r[i-1])*(s[n]-s[j]+s[i-1]));
if(j+1<=n+1)
d[i][j][k]=min(d[i][j][k],dp(i,j+1,1)+abs(r[i]-r[j+1])*(s[n]-s[j]+s[i-1]));
}
else if(k==1)
{
if(i-1>=0)
d[i][j][k]=min(d[i][j][k],dp(i-1,j,0)+abs(r[j]-r[i-1])*(s[n]-s[j]+s[i-1]));
if(j+1<=n+1)
d[i][j][k]=min(d[i][j][k],dp(i,j+1,1)+abs(r[j]-r[j+1])*(s[n]-s[j]+s[i-1]));
}
return d[i][j][k];
}
int main()
{
cin>>n>>v;
s[0]=0;
for(long i=1;i<=n;i++)
{
cin>>r[i]>>w[i];
s[i]=s[i-1]+w[i];
}
// Input
memset(d,-1,sizeof(d));
d[0][n+1][0]=d[0][n+1][1]=0;
// Init
cout<<dp(v,v,0)<<endl;
// Output
return 0;
}
posted on 2010-10-30 20:15
lee1r 閱讀(566)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃