Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DP算法,先排序后DP,WA,附程序

Posted by loveob at 2007-08-14 08:17:29 on Problem 1088
是不是我对题目的理解有问题
假如输入样例的最优解为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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator