bzoj3892[Usaco2014 Dec]Marathon*

bzoj3892[Usaco2014 Dec]Marathon

题意：

在二维平面上有N个点，从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。求从1号点出发，按从1到N的顺序依次到达每个点的最小总代价。你有K次机会可以跳过某个点，不允许跳过1号点或N号点。n≤500。

题解：

dp。f[i][j]表示当前在i个点，剩j次，则f[i][j]=min(f[i+1][j]+abs(x[i+1]-x[i])+abs(y[i+1]-y[i]),f[i+k+1][j-k]),i+k+1≤n,k≤j。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 510

 using namespace std;

 inline int read(){

     char ch=getchar(); int f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int n,k,x[maxn],y[maxn],dp[maxn][maxn];

 int dfs(int a,int b){

     if(a==n)return ; if(dp[a][b]!=-)return dp[a][b];

     dp[a][b]=dfs(a+,b)+abs(x[a]-x[a+])+abs(y[a]-y[a+]);

     inc(i,,min(b,n-a-))dp[a][b]=min(dp[a][b],dfs(a+i+,b-i)+abs(x[a]-x[a+i+])+abs(y[a]-y[a+i+]));

     return dp[a][b];

 }

 int main(){

     n=read(); k=read(); inc(i,,n)x[i]=read(),y[i]=read(); memset(dp,-,sizeof(dp));

     printf("%d",dfs(,k)); return ;

 }

20160909

巴特西

bzoj3892[Usaco2014 Dec]Marathon*

最新文章

热门文章