Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
DP算法,先排序后DP,WA,附程序是不是我对题目的理解有问题 假如输入样例的最优解为24-17-16-1,那是不是应该输出4啊? 还有,对于 1 1 1 应该输出1还是0? #include<iostream> using namespace std; struct node { int x,y; node() { x=y=0; } }; int main() { int r,c,i,j,h[102][102],a[102][102],k;node p[10002],t; cin>>r>>c; memset(h,10001,sizeof(h)); memset(a,1,sizeof(a)); for (i=1;i<=r;i++) for (j=1;j<=c;j++) {cin>>h[i][j];a[i][j]=h[i][j];p[(i-1)*r+j].x=i;p[(i-1)*r+j].y=j;} for (i=1;i<=r*c;i++) for (j=1;j<=r*c-i;j++) if (h[p[j].x][p[j].y]>h[p[j+1].x][p[j+1].y]) {t=p[j];p[j]=p[j+1];p[j+1]=t;} for (i=1;i<=r*c;i++) { k=0; if ((h[p[i].x][p[i].y]>h[p[i].x+1][p[i].y])&&(a[p[i].x][p[i].y]<a[p[i].x+1][p[i].y])) k=a[p[i].x+1][p[i].y]; if ((h[p[i].x][p[i].y]>h[p[i].x-1][p[i].y])&&(a[p[i].x][p[i].y]<a[p[i].x-1][p[i].y])) k=a[p[i].x-1][p[i].y]; if ((h[p[i].x][p[i].y]>h[p[i].x][p[i].y+1])&&(a[p[i].x][p[i].y]<a[p[i].x][p[i].y+1])) k=a[p[i].x][p[i].y+1]; if ((h[p[i].x][p[i].y]>h[p[i].x][p[i].y-1])&&(a[p[i].x][p[i].y]<a[p[i].x][p[i].y-1])) k=a[p[i].x][p[i].y-1]; a[p[i].x][p[i].y]+=k; } k=0; for (i=1;i<=r;i++) for(j=1;j<=c;j++) if (a[i][j]>k) k=a[i][j]; cout<<k<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator