#include <stdio.h>
#include <math.h>

double a[1010][1010];
int x[1000],y[1000];

int main()
{
	int n,e,nn,ee,i,j,temp;
	double re1,re2,re3,max,mmax;
	for (i=0;i<1010;i++) for (j=0;j<1010;j++) a[i][j]=0.0;
	scanf("%d%d",&n,&e);
	for (nn=0;nn<n-1;nn++) scanf("%d",&x[nn]);
	for (ee=0;ee<e-1;ee++) scanf("%d",&y[ee]);
	for (nn=n-1;nn>=0;nn--) for (ee=e-1;ee>=0;ee--) {
		if (nn==n-1) if (ee==e-1) continue;
		if (nn!=n-1) if (ee!=e-1) {
			re1=a[nn+1][ee+1]+sqrt(x[nn]*x[nn]+y[nn]*y[nn]);
			re2=a[nn+1][ee]+y[nn];
			re3=a[nn][ee+1]+x[nn];
			max=re1;
			if (re2<max) max=re2;
			if (re3<max) max=re3;
			a[nn][ee]=max;
		}
		if (nn!=n-1) if (ee==e-1) a[nn][ee]=y[nn]+a[nn+1][ee];
		if (nn==n-1) if (ee!=e-1) a[nn][ee]=x[ee]+a[nn][ee+1];
	}
	mmax=a[0][0];
	for (ee=0;ee<=e/2-1;ee++) {temp=y[ee];y[ee]=y[e-2-ee];y[e-2-ee]=temp;}
	for (nn=n-1;nn>=0;nn--) for (ee=e-1;ee>=0;ee--) {
		if (nn==n-1) if (ee==e-1) continue;
		if (nn!=n-1) if (ee!=e-1) {
			re1=a[nn+1][ee+1]+sqrt(x[nn]*x[nn]+y[nn]*y[nn]);
			re2=a[nn+1][ee]+y[nn];
			re3=a[nn][ee+1]+x[nn];
			max=re1;
			if (re2<max) max=re2;
			if (re3<max) max=re3;
			a[nn][ee]=max;
		}
		if (nn!=n-1) if (ee==e-1) a[nn][ee]=y[nn]+a[nn+1][ee];
		if (nn==n-1) if (ee!=e-1) a[nn][ee]=x[ee]+a[nn][ee+1];
	}
	if (a[0][0]>mmax) mmax=a[0][0];
	i=0;
	while (i<mmax-1e-10) i++;
	printf("%d\n",i);
	return 0;
}

• 算一下对角线就可以了吧？ (1499) sothink 2004-12-08 19:04:25
  • Re:算一下对角线就可以了吧？ (30) seol 2004-12-08 20:37:03
    • 算整个矩形的对角线就可以了 (36) sspp 2004-12-08 21:22:58
      • 啊？原来是这样啊！嘻嘻，谢谢了！ (5) seol 2004-12-09 12:21:08