本文主要是介绍hdu 4628 ——Pieces，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
记忆化搜索+状态压缩
一直超时，看了标程后改了一个地方。
自己还是太菜啊
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 16
#define INF 1<<30
char a[maxn+1];
int pali[1<<maxn];//是否是回文
int dp[1<<maxn];//需要的step
int n;
int dfs(int x)
{if(dp[x]!=-1)return dp[x];int ans=INF;
/*for(int i=x;i>=1;i--)// 以前是这么写 超时了 if(pali[i]&&(x|i==x))ans=min(dfs(x-i)+1,ans);
*/for(int i=x;i>=1;(--i)&=x)if(pali[i]&&(x|i==x))ans=min(dfs(x-i)+1,ans);return dp[x]=ans;
}
bool judge(int x)
{char str[maxn];int cnt=0;for(int i=0;i<n;i++) if(x>>i&1)str[cnt++]=a[n-i-1];for(int l=0,r=cnt-1;l<r;++l,--r)if(str[l]!=str[r])return 0;return 1;
}
int main()
{int t;cin>>t;while(t--){cin>>a;n=strlen(a);memset(pali,0,sizeof(pali));memset(dp,-1,sizeof(dp));for(int i=0;i<(1<<n);i++)if(judge(i)){pali[i]=1;dp[i]=1;}dp[0]=0;int ans=dfs((1<<n)-1);printf("%d\n",ans); }return 0;
}
非递归
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 16
#define INF 1<<30
char a[maxn+1];
int pali[1<<maxn];//是否是回文
int vis[1<<maxn];
int n;
void bfs(int x)
{queue<int> q;q.push(x);vis[x]=0;while(!q.empty()){int u=q.front();q.pop();if(u==0)return;for(int i=u;i>=1;(--i)&=u)if(pali[i]&&(u|i==u)&&vis[u-i]==-1){q.push(u-i);vis[u-i]=vis[u]+1;}}
}
bool judge(int x)
{char str[maxn];int cnt=0;for(int i=0;i<n;i++) if(x>>i&1)str[cnt++]=a[n-i-1];for(int l=0,r=cnt-1;l<r;++l,--r)if(str[l]!=str[r])return 0;return 1;
}
int main()
{int t;cin>>t;while(t--){cin>>a;n=strlen(a);memset(pali,0,sizeof(pali));memset(vis,-1,sizeof(vis));for(int i=0;i<(1<<n);i++)if(judge(i))pali[i]=1;bfs((1<<n)-1);printf("%d\n",vis[0]); }return 0;
}
这篇关于hdu 4628 ——Pieces的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
