UVa10651(記憶化搜索)

題意:

給一串-和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;
}