为什么不行。。。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define maxn 5010
#define INF 66666666
#define min(a,b) (a)>(b)?(b):(a)
#define Mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
string a, b; int n;
int num[2][maxn]; ///记录中间结果的数组
void LCS(){
    int e = 0;
    for (int i = 0; i < n; ++i){//求公共子序列的最大长度  
        e = 1 - e;//这里使用了滚动数组,因为直接开num[5000][5000]会内存溢出...  
        for (int j = 0; j < n; ++j){
            if (a[i] == b[j]){
                num[e][j] = num[1 - e][j - 1] + 1;
            }
            else{
                num[e][j] = max(num[1 - e][j], num[e][j - 1]);
            }
        }
    }
    cout << n - num[e][n - 1] << endl;
}
int main(){
    cin >> n;
    cin >> a;
    b = a;
    reverse(b.begin(), b.end());
    Mem(num, 0);
    LCS();
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1327
难度
6
分类
动态规划 点击显示
标签
递交数
2550
已通过
773
通过率
30%
被复制
4
上传者