uva111 - History Grading(최대 공통 하위 시퀀스 LCS)

제목: 가장 긴 공공 서열 문제의 사고방식을 구합니다: dp, 그리고 구덩이가 있습니다!제목은 이 서열이 정확한 서열의 몇 위에 있는지, 또 바꾸어야 한다는 것이다.그리고 또 하나, 아래의 코드 AC는 사실 오류가 있고, 오류가 있는 부분은 코드 부분에서 언급될 것이다.잘못된 이유http://blog.csdn.net/conatic/article/details/50848324코드는 다음과 같습니다.
#include 
#include 
#include 
#include 
using namespace std;
const int N = 35;
int a[N], b[N], dp[N][N];

int main() {
    int n, t;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)  {
        scanf("%d", &t);
        a[t] = i;
    }
    while (~scanf("%d", &t)) {
        b[t] = 1;
        for (int i = 2; i <= n; i++) {
            scanf("%d", &t);
            b[t] = i;
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (a[i] == b[j])
                /*     ,   AC ,        uva10405  ,    :
        for (int i = 1; i <= la; i++) {
            for (int j = 1; j <= lb; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

            }
        }*/
                    dp[i][j] ++;
            }
        }
        printf("%d
"
, dp[n][n]); } return 0; }

좋은 웹페이지 즐겨찾기