단순 동적 계획(POJ 1609 Tiling Up Blocks 문제 해결 보고서)

이 문제를 보니 올해 다교의 한 문제처럼 느껴졌는데 데이터 n의 크기가 10^4에 이르렀다. 그러면 건도달리기를 하려면 T가 필요하다. 건도의 복잡도가 N^2가 많지 않기 때문에 다교의 그 문제를 사용할 수 없다.
우리가 보여준 l과 r의 데이터 범위가 비교적 작다는 것을 보면 1에서 100이다. 그러면 우리는 dp 데이터로 dp[i][j]가 (i, j)가 나타난 횟수를 나타낸다. 그리고 우리가 제목에 따라 요구하는 규칙에 따라 i>=i'&&&j>=j'가 필요하다. 그래서 우리는 상태 dp[i][j]는 i'<=i&j'<=j'<=j'의 가장 큰 누적화를 나타낸다. 그러면 우리는 상태 이동 방정식을 다음과 같이 찾을 수 있다.마지막으로 Blocks를 출력하는 데 대응하는 가장 큰 누적과 요구되는 높이입니다.
아래에 내 코드를 첨부합니다(비교적 간결하다).

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Max=10010;
typedef struct NODE
{
    int l,r;
    NODE(){}
    NODE(int tl,int tr)
    {
        l=tl;
        r=tr;
    }
}Node;
Node blocks[Max];

int dp[110][110];
int main()
{
    int n,ans;
    while(scanf("%d",&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&blocks[i].l,&blocks[i].r);
            dp[blocks[i].l][blocks[i].r]++;
        }
        for(int i=1;i<=100;i++)
        {
            for(int j=1;j<=100;j++)
            {
                dp[i][j]+=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(dp[blocks[i].l][blocks[i].r]>ans)
                ans=dp[blocks[i].l][blocks[i].r];
        }
        printf("%d
",ans);
    }
    printf("*
");
    return 0;
}