程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-4628 Pieces 狀壓DP

HDU-4628 Pieces 狀壓DP

編輯:C++入門知識

HDU-4628 Pieces 狀壓DP


給出一行字符串,每次可以刪去一個回文子串,子串可以是不連續的,因此用狀壓比較好模擬,求刪掉整個字符串需要的最少步數。

字符串的最大長度為16,因此不能逐行枚舉狀態,首先預處理出來所有的的回文子串,然後從第一步開始,依次狀壓第i步能到達的狀態,如果能達到母串,跳出。

還有初始化不要用圖省事用memset。。不優越的姿勢+函數導致T了數發。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
char s[20];
char s1[20];
int ans;
int num;
int dp[1<<17][17];
int visit[20];
int Pow[15];
int a[1<<17];
bool solve(char str[])
{
	int flag=1;
	int start=0;
	int end=strlen(str)-1;
	while(start<=end)
	{
		if(str[start]!=str[end])
		{
			flag=0;
			break;
		}
		start++;
		end--;
	}
	if(flag)
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	int t;
	int sum;
	Pow[0]=1;
	for(int i=1;i<=18;i++)
	{
		Pow[i]=Pow[i-1]*2;
	}
	scanf("%d",&t);
	while(t--)
	{
		num=0;
		scanf("%s",s);
		int len=strlen(s);
		int mos=1<<(len);
		for(int i=1;i<=len;i++)
		{
			for(int j=1;j

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved