HDU 多校第三场

HDU 4628 Pieces

状态压缩dp，dp功底还是太弱了

[cpp]
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
# define N 16
using namespace std;
//状态i的二进制中，1表示该位字符存在，0表示不存在
int dp[1 << N],nice[1 << N]; //dp[i]表示i状态下，删除剩余字符需要的最少步数，nice[i]表示状态i下，他是否是回文
char str[N];

void init() {
    memset(dp,0,sizeof(dp));
    memset(nice,0,sizeof(nice));
}

int dfs(int n) {
    if(dp[n] != 0) return dp[n];
    int ans = 100;
    for(int i=n; i>=1; i &= n,i--) {// i & n 则舍去了诸多不能由i转化到n的状态

        if(nice[i] && (i|n) == n) {
            ans = min(ans,dfs(n-i)+1);
        }
    }
    return dp[n] = ans;
}

int main() {
    int T;
    cin >> T;
    while(T --) {
        init();
        scanf("%s",str);
        int len = strlen(str);
        int n = 1 << len;
        for(int i=0; i<n; i++) {
            int cnt = 0; char tmp[N];
            for(int j=0; j<len; j++) {
                if((i>>j) & 1) {//表示i右移j位，末尾是零还是一
                    tmp[cnt ++] = str[len-1-j];
                }
            }
            int l,r,flag = 1;
            for(l=0,r=cnt-1; l<r; l++,r--) {
                if(tmp[l] != tmp[r]) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1) {

                nice[i] = 1;
                dp[i] = 1;
            }
        }
        printf("%d\n",dfs(n-1));
    }
    return 0;
}

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
# define N 16
using namespace std;
//状态i的二进制中，1表示该位字符存在，0表示不存在
int dp[1 << N],nice[1 << N]; //dp[i]表示i状态下，删除剩余字符需要的最少步数，nice[i]表示状态i下，他是否是回文
char str[N];

void init() {
memset(dp,0,sizeof(dp));
memset(nice,0,sizeof(nice));
}

int dfs(int n) {
    if(dp[n] != 0) return dp[n];
    int ans = 100;
    for(int i=n; i>=1; i &= n,i--) {// i & n 则舍去了诸多不能由i转化到n的状态

        if(nice[i] && (i|n) == n) {
            ans = min(ans,dfs(n-i)+1);
        }
    }
    return dp[n] = ans;
}

int main() {
    int T;
    cin >> T;
    while(T --) {
        init();
        scanf("%s",str);
        int len = strlen(str);
        int n = 1 << len;
        for(int i=0; i<n; i++) {
            int cnt = 0; char tmp[N];
            for(int j=0; j<len; j++) {
                if((i>>j) & 1) {//表示i右移j位，末尾是零还是一
                    tmp[cnt ++] = str[len-1-j];
                }
            }
            int l,r,flag = 1;
            for(l=0,r=cnt-1; l<r; l++,r--) {
                if(tmp[l] != tmp[r]) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1) {

                nice[i] = 1;
                dp[i] = 1;
            }
        }
        printf("%d\n",dfs(n-1));
    }
    return 0;
}

HDU 4630 No Pain No Game

思路：考虑从左到右扫描，对于每个数，记录在它之前出现，并且最靠右边的那个它的倍数，用previ表示。考虑当前数i的所有约数x，对于所有r >= i,l <= previ 的询问，x就是可能的答案了。

用树状数组或者线段树维护（此题线段树速度巨慢）因为n只有5W，可以预处理好倍数约数关系

补充：软件开发 , C++ ,