soj2381三维dp.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 77 行

#include<stdio.h>
#include<string.h>

int main(void)
{
    int a[105];
    int n;
    while(scanf("%d",&n)==1)
    {
        if(n==-1)
            break;
        int i;
        a[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int dp[105][105]={0};

        for(i=1;i<=n;i++)
        {
            dp[i][0]=dp[0][i]=1;
        }
        int j,k;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<i;j++)
            {
                for(k=0;k<i;k++)
                {
                    if(j!=k)
                    {
                        if(j==0||k==0)
                        {
                            if(j==0)
                            {
                                if(a[i]<=a[k])
                                {
                                    dp[i][k] = dp[i][k] > dp[j][k]+1?dp[i][k]:dp[j][k]+1;
                                    dp[j][i] = dp[j][i] > dp[j][k]+1?dp[j][i]:dp[j][k]+1;
                                }
                            }
                            else
                            {
                                if(a[i]>=a[j])
                                {
                                    dp[i][k] = dp[i][k] > dp[j][k]+1?dp[i][k]:dp[j][k]+1;
                                    dp[j][i] = dp[j][i] > dp[j][k]+1?dp[j][i]:dp[j][k]+1;
                                }
                            }
                        }
                        else
                        {
                            if(a[i]<=a[k]&&a[i]>=a[j])
                            {
                                dp[i][k] = dp[i][k] > dp[j][k]+1?dp[i][k]:dp[j][k]+1;
                                dp[j][i] = dp[j][i] > dp[j][k]+1?dp[j][i]:dp[j][k]+1;
                            }
                        }
                    }
                }
            }
        }
        int result=0;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(result<dp[i][j])
                    result=dp[i][j];
            }
        }
        printf("At most %d book(s) can be put onto the bookshelf.\n",result);
    }
    return 0;
}