UVa 10651 Pebble Solitaire (DPbitset)

本文主要是介绍UVa 10651 Pebble Solitaire (DPbitset)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

10651 - Pebble Solitaire

Time limit: 3.000 seconds 

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1592

化为二进制进行状态转移，详见代码。

完整代码：

/*0.016s*/#include<bits/stdc++.h>
using namespace std;
const int Size = 12;char str[Size];
int dp[4100];
bitset<Size> tmp;int f(unsigned long n)
{if (n == 0 || dp[n]) return dp[n];bitset<Size> b(n);int minn = b.count();///在不卡时间的情况下，我使用bitset就是因为这个函数挺方便的，虽然自己写也不过几行///用bitset还可以避免因运算符优先级造成的麻烦（! ~ 高于 << >> 高于 == 高于 & 高于 ^ 高于 | 高于 && 高于 ||）for (int i = 0; i < Size; ++i){if (!b.test(i))///等价于if((n>>i&1)==0){if (i < Size - 2 && b.test(i + 1) && b.test(i + 2)){tmp = b;tmp.set(i), tmp.reset(i + 1), tmp.reset(i + 2);///等价于n|1u<<i,n&~(1u<<(i+1)),n&~(1u<<(i+2))minn = min(minn, f(tmp.to_ulong()));}if (i > 1 && b.test(i - 1) && b.test(i - 2)){tmp = b;tmp.set(i), tmp.reset(i - 1), tmp.reset(i - 2);minn = min(minn, f(tmp.to_ulong()));}}}return dp[n] = minn;
}int main()
{int t, i;scanf("%d", &t);while (t--){getchar();for (i = 0; i < Size; ++i)str[i] = (getchar() == '-' ? '0' : '1');printf("%d\n", f(strtoul(str, NULL, 2)));}return 0;
}

这篇关于UVa 10651 Pebble Solitaire (DPbitset)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---