UVa 10651 Pebble Solitaire：DP&bitset

UVa 10651 Pebble Solitaire：DP&bitset2014-07-28 csdn博客 synapse7

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
", f（strtoul（str, NULL, 2）））;}return 0;}