| ||||||||||
| 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