首页 > ACM题库 > HDU-杭电 > Hdu 1726 God’s cutter-动态规划[解题报告] C++
2013
12-21

Hdu 1726 God’s cutter-动态规划[解题报告] C++

God’s cutter

问题描述 :

有一张长纸条, 上面写有n(0<n<=100)个大写字母, 它们或者是X, 或者是O.
现在需要将其剪成许多小长条, 使得每个小长条上的字串都关于其中心对称.
例如: O, XX, OXO, XOXXOX等. 求满足要求的最少剪裁次数.

输入:

每行表示一组测试数据, 给出一个只包含O和X的字符串.

输出:

对每组测试数据输出一个数, 表示最小剪裁次数.

样例输入:

XOOXO
XXOXOO
XOXOXOX

样例输出:

1
2
0


简单的一维DP,状态转移方程 f[i]=min(f[j]+1) 其中 0=

#include<stdio.h>
#include<string.h>
#define oo 100000000
#define M 105
int map[M][M];
char str[M];

bool judge(int x, int y) {
    int i, k = (y – x + 1) / 2;
    for (i = 0; i < k; i++)
        if (str[x + i] != str[y - i])return false;
    return true;
}

int main() {
    int f[M], n, i, j;
    while (scanf("%s", str) != EOF) {
        n = strlen(str);
        for (i = 0; i < n; i++)
            for (j = i; j < n; j++) {
                if (judge(i, j))map[i][j] = 1;
                else map[i][j] = 0;
            }
        f[0] = 0;
        for (i = 1; i < n; i++) {
            f[i] = oo;
            if (map[0][i])f[i] = 0;
            else {
                for (j = 0; j < i; j++)
                    if (map[j + 1][i] && f[j] + 1 < f[i])
                        f[i] = f[j] + 1;
            }
        }
        printf("%d\n", f[n - 1]);
    }
    return 0;
}