当前位置:编程学习 > C/C++ >>

Uva - 10651 - Pebble Solitaire

题意:12个位置,有些有鹅卵石,有些是空的,2个连续的鹅卵石,
如果其左边连着的那个是空的,那么第二个鹅卵石可移动到那个空的位置上,并移除第1个鹅卵石;
如果其右边连着的那个是空的,那么第一个鹅卵石可移动到那个空的位置上,并移除第2个鹅卵石。
问最后最少可以剩下多少个鹅卵石。
 option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=1592
——>>
状态压缩
判断其若未是不可移动的最终态,则继续进行dp,怎么判?12个位置3个3个扫一次即可。
[cpp] v 
#include  
  
using namespace std;  
  
int minn;  
int dp(int x)  
{  
    int i, cnt = 0;  
    for(i = 1; i <= 10; i++)  
        if(((x&(1<<(i-1))) && (x&(1<
        {  
            x ^= (1<<(i-1));  
            x ^= (1<
            x ^= (1<<(i+1));  
            int temp = dp(x);  
            if(temp < minn) minn = temp;        //更新最小值  
            x ^= (1<<(i-1));        //回溯  
            x ^= (1<
            x ^= (1<<(i+1));        //回溯  
            cnt++;  
        }  
    if(cnt == 0)        //判断是否为最终态  
    {  
        int ans = 0;  
        for(i = 0; i < 12; i++)  
            if(x&(1<
        if(ans < minn) minn = ans;  
    }  
    return minn;  
}  
int main()  
{  
    char s[15];  
    int T, i;  
    cin>>T;  
    while(T--)  
    {  
        cin>>s;  
        int a = 0;  
        for(i = 0; i < 12; i++)  
            if(s[i] == 'o') a = a^(1<
        minn = (1<<30);  
        cout<
    }  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,