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);
补充:软件开发 , C++ ,