首页 > 代码库 > bzoj3892[Usaco2014 Dec]Marathon*

bzoj3892[Usaco2014 Dec]Marathon*

2024-08-13 13:18:09   217人阅读

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。
代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 510 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11     while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12     return f*x;13 }14 int n,k,x[maxn],y[maxn],dp[maxn][maxn];15 int dfs(int a,int b){16     if(a==n)return 0; if(dp[a][b]!=-1)return dp[a][b];17     dp[a][b]=dfs(a+1,b)+abs(x[a]-x[a+1])+abs(y[a]-y[a+1]);18     inc(i,1,min(b,n-a-1))dp[a][b]=min(dp[a][b],dfs(a+i+1,b-i)+abs(x[a]-x[a+i+1])+abs(y[a]-y[a+i+1]));19     return dp[a][b];20 }21 int main(){22     n=read(); k=read(); inc(i,1,n)x[i]=read(),y[i]=read(); memset(dp,-1,sizeof(dp));23     printf("%d",dfs(1,k)); return 0;24 }

 

20160909

bzoj3892[Usaco2014 Dec]Marathon*


联系
我们