USACO16JAN Radio Contact 发表于 2018-08-04 | 分类于 USACO | 字数统计: 387 字 题目地址 题解水DP。按照时间变化递推即可。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cctype>#define INF 2000000000using namespace std;typedef long long ll;int read(){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; }int n,m,pos1[1005][2],pos2[1005][2],f[1005][1005];char s1[1005],s2[1005];void movement(char c,int &x,int &y){ if(c=='N')y++;if(c=='S')y--; if(c=='E')x++;if(c=='W')x--;}int sqr(int a,int b){ return (pos1[a][0]-pos2[b][0])*(pos1[a][0]-pos2[b][0])+ (pos1[a][1]-pos2[b][1])*(pos1[a][1]-pos2[b][1]);}void init(){ n=read(),m=read(); pos1[0][0]=read(),pos1[0][1]=read(); pos2[0][0]=read(),pos2[0][1]=read(); scanf("%s%s",s1+1,s2+1); for(int i=1,x=pos1[0][0],y=pos1[0][1];i<=n;i++) movement(s1[i],x,y), pos1[i][0]=x,pos1[i][1]=y; for(int i=1,x=pos2[0][0],y=pos2[0][1];i<=m;i++) movement(s2[i],x,y), pos2[i][0]=x,pos2[i][1]=y;}void solve(){ memset(f,0x14,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+sqr(i,0); for(int i=1;i<=m;i++) f[0][i]=f[0][i-1]+sqr(0,i); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=min(f[i-1][j],f[i][j-1]), f[i][j]=min(f[i][j],f[i-1][j-1]), f[i][j]+=sqr(i,j); printf("%d\n",f[n][m]);}int main(){ init(); solve(); return 0;}
v1.5.2