心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
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 阅读(338) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理