HDU 4628 Pieces
状态压缩dp，dp功底还是太弱了
[cpp]
#include
#include
#include
#include
# 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 int cnt = 0; char tmp[N];
for(int j=0; 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 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
#include
#include
#include
# 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 int cnt = 0; char tmp[N];
for(int j=0; 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 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，可以预处理好倍数约数关系
[cpp]
#include
#include
#include
#include
#include
#include
# define MAX 51111
# define ll(x) x << 1
# define rr(x) x << 1 | 1
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
int a[MAX],pos[MAX],print[MAX];
struct node {
int l,r;
int num;
}ask[MAX];
struct Node {
int s,e,next;
}v[1111111];
int head[MAX];
int n,q,num = 0;
void addedge(int s,int e) {
v[num].s = s;
v[num].e = e;
v[num].next = head[s];
head[s] = num++;
}
void init() { //预处理
memset(head,-1,sizeof(head));
for(int i=1; i<=50000; i++) {
for(int j=i; j<=50000; j+=i) {
addedge(j,i);
}
}
}
bool cmp(node a,node b) {
return a.r < b.r;
}
struct Tree {
in