频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
UVa10651(记忆化搜索)
2013-07-29 16:41:45           
收藏   我要投稿

题意:

给一串-和o组成的字符串,你可以把“-oo"变成”o--",可以把“oo-”变成“--o",问最后最少有多少个o.

 


状态压缩 ,记忆化搜索


code:


 

 #include <stdio.h>  
#include <string.h>  
#define len 12  
#define min(a,b) (((a)<(b)) ?(a):(b))  
int d[1<<13]; 
int dp(int n) 
{ 
    int i, t; 
    if(d[n]!=-1) return d[n]; 
    d[n] = 0; 
    for(i=0; i<len; i++) 
        if(n&(1<<i)) 
            d[n]++; 
    for(i=0; i<len-2; i++) 
    { 
        t = n; 
        if( (t&(1<<i)) && (t&(1<<(i+1))) && !(t&(1<<(i+2))) ) 
        { 
            t &=~(1<<i); 
            t &=~(1<<(i+1)); 
            t |=1<<(i+2); 
            d[n] = min(d[n],dp(t)); 
        } 
        if( !(t&(1<<i)) && (t&(1<<(i+1))) && (t&(1<<(i+2))) ) 
        { 
            t &=~(1<<(i+1)); 
            t &=~(1<<(i+2)); 
            t |=1<<i; 
            d[n] = min(d[n],dp(t)); 
        } 
    } 
    return d[n]; 
} 
int main() 
{ 
    int T, i, n; 
    char str[20]; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%s",str); 
        n = 0; 
        for(i=0; i<len; i++) 
            if(str[i]=='o') 
                n ^=1<<i; 
        memset(d,-1,sizeof(d)); 
        printf("%d\n", dp(n)); 
    } 
    return 0; 
} 

#include <stdio.h>
#include <string.h>
#define len 12
#define min(a,b) (((a)<(b)) ?(a):(b))
int d[1<<13];
int dp(int n)
{
    int i, t;
    if(d[n]!=-1) return d[n];
    d[n] = 0;
    for(i=0; i<len; i++)
        if(n&(1<<i))
            d[n]++;
    for(i=0; i<len-2; i++)
    {
        t = n;
        if( (t&(1<<i)) && (t&(1<<(i+1))) && !(t&(1<<(i+2))) )
        {
            t &=~(1<<i);
            t &=~(1<<(i+1));
            t |=1<<(i+2);
            d[n] = min(d[n],dp(t));
        }
        if( !(t&(1<<i)) && (t&(1<<(i+1))) && (t&(1<<(i+2))) )
        {
            t &=~(1<<(i+1));
            t &=~(1<<(i+2));
            t |=1<<i;
            d[n] = min(d[n],dp(t));
        }
    }
    return d[n];
}
int main()
{
    int T, i, n;
    char str[20];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str);
        n = 0;
        for(i=0; i<len; i++)
            if(str[i]=='o')
                n ^=1<<i;
        memset(d,-1,sizeof(d));
        printf("%d\n", dp(n));
    }
    return 0;
}

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 记忆
上一篇:push方法的页面间跳转--
下一篇:C/C++单链表
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站