DP題，狀態總量為2^12，其實可以用對稱性減少一半狀態數。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/3 12:18:41
* File Name: uva10651.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
int d[4107];
int dp(int x)
{
if(d[x]!=-1)
return d[x];
d[x]=0;
for(int i=0;i<12;i++)
if(x&(1<<i))
d[x]++;
for(int i=0;i<10;i++)
if((x&(1<<i)) && (x&(1<<(i+1))) && !(x&(1<<(i+2))))
{
int newx(x);
newx=(~((~newx)|(1<<i)));
newx=(~((~newx)|(1<<(i+1))));
newx=(newx|(1<<(i+2)));
d[x]=min(d[x],dp(newx));
}
for(int i=0;i<10;i++)
if(!(x&(1<<i)) && (x&(1<<(i+1))) && (x&(1<<(i+2))))
{
int newx(x);
newx=(~((~newx)|(1<<(i+1))));
newx=(~((~newx)|(1<<(i+2))));
newx=(newx|(1<<i));
d[x]=min(d[x],dp(newx));
}
return d[x];
}
int main()
{
//freopen("data.in","r",stdin);
memset(d,-1,sizeof(d));
int T;
cin>>T;
while(T--)
{
string s;
cin>>s;
int n(0);
for(int i=0;i<s.size();i++)
if(s[i]=='o')
n=(n|(1<<i));
printf("%d\n",dp(n));
}
return 0;
}
posted on 2011-08-03 19:27
lee1r 閱讀(375)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃