USACO 2016 January Contest Gold T2: Radio Contact

题目大意

FJ失去了他最喜欢的牛铃,而Bessie已经同意帮助他找到它!他们用不同的路径搜索农场,通过无线电保持联系。不幸的是,无线电中的电池电量不足,所以他们设法尽可能保持两者位置的距离最小,以节省电量。

FJ从位置(fx,fy)开始,并计划遵循由N步骤组成的路径,每个步骤都是“N”(北),“E”(东),“S”(南),或“W”(西)。Bessie从位置(bx,by)开始,并遵循由M步骤组成的类似路径。两个路径可以经过相同的点。在每个时间段,FJ可以保持在他现在的位置,或沿着他的道路前进一步,无论哪个方向恰好在下一个(假设他还没有到达他的路径的最后位置)。Bessie可以做出类似的选择。在每个时间步(不包括从初始位置开始的第一步),他们的无线电消耗的能量等于它们之间距离的平方。

请帮助FJ和Bessie计划行动策略,最大限度地减少消耗的能量总量。总量包括最终步骤,这时两者首先到达各自路径上的最终位置。

 

第一行输入N和M(1≤N,M≤1000)。

第二行输入整数fx和fy,第三行输入bx和by(0≤fx,fy,bx,≤1000)。下一行包含一个长度为N的字符串描述FJ的路径,最后一行包含一个字符串的长度M描述Bessie的路径。

数据满足(0≤x,y≤1000)。注意,东方向为正X方向,北方向为正Y方向。

题目分析

观察可知,FJ 与 Bessie的路径相对独立,且题目让我们寻找最优行动策略,不难想到DP。

令 f[i][j] 表示当FJ走了i步,Bessie走了j步时的最小能量损耗。

转移就显而易见了,f[i][j] = min (f[i-1][j] , f[i-1][j-1] , f[i][j-1] ) + FJ与Bessie当前距离。

最后 f[n][m] 即最优策略。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int MAXN=1005;
 5 
 6 ll dp[MAXN][MAXN];
 7 int n,m;
 8 int fx,fy,bx,by,lf,lb;
 9 char f[MAXN],b[MAXN];
10 
11 inline void Move(int &x,int &y,char dir){
12     switch(dir){
13         case 'N':y++;break;
14         case 'S':y--;break;
15         case 'W':x--;break;
16         case 'E':x++;break;
17     }
18 }
19 inline ll Calc(int x,int y,int xx,int yy){
20     return (x-xx)*(x-xx)+(y-yy)*(y-yy);
21 }
22 int main(){
23     scanf("%d%d",&n,&m);
24     scanf("%d%d%d%d",&fx,&fy,&bx,&by);
25     scanf("%s%s",f+1,b+1);
26     lf=strlen(f+1);lb=strlen(b+1);
27     int fxx=fx,fyy=fy,bxx=bx,byy=by;
28     for(int i=1;i<=lf;++i){
29         Move(fxx,fyy,f[i]);
30         dp[i][0]=dp[i-1][0]+Calc(fxx,fyy,bx,by);
31     }
32     for(int i=1;i<=lb;++i){
33         Move(bxx,byy,b[i]);
34         dp[0][i]=dp[0][i-1]+Calc(fx,fy,bxx,byy);
35     }
36     fxx=fx;fyy=fy;
37     for(int i=1;i<=lf;++i){
38         bxx=bx;byy=by;
39         Move(fxx,fyy,f[i]);
40         for(int j=1;j<=lb;++j){
41             Move(bxx,byy,b[j]);
42             dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
43             dp[i][j]+=Calc(fxx,fyy,bxx,byy);
44         }
45     }
46     printf("%lld\n",dp[lf][lb]);
47     return 0;
48 }

 

上一篇:USACO 2005 December Gold - Layout (差分约束)


下一篇:python字典讲解