宿州市住房和城乡建设局网站,新闻式软文经典案例,郑州专业网站优化,发布消息做任务的网站点击打开链接 题意#xff1a; 给出一个序列#xff0c;其中距离不超过6的两个相同的数字可以消除掉#xff08;从上往下消#xff0c;输入是从底向上的#xff09;#xff0c;问能不能全部消除。 思路#xff1a; 状压dp http://www.cnblogs.com/swm8023/archive/2012/…点击打开链接 题意 给出一个序列其中距离不超过6的两个相同的数字可以消除掉从上往下消输入是从底向上的问能不能全部消除。 思路 状压dp http://www.cnblogs.com/swm8023/archive/2012/09/10/2679455.html 因为最坏情况下它后面的四个数字能被它前面的四个数字消掉这样它就能和原来是它后面的第9个元素相消了最多10个状态 状态转移 如果st的第1说明这一位位为0已经被消掉,d[i][st]dp(i1,next(st))。 如果第1为为1向后连续找至多五个为1的位比较是否和第一位数字相同如果相同就将st的这两位置为0然后 d[i][st]d(i1,next(newst)),newstst~1~(1k)其中x[k]x[i]。 next(st)这个函数是求将st传递到下一个位置时的状态如果n-(p1) 9 st19|st1否则stst1,因为只有当后面数字多于10个时才会有新的数字加入到状态中。 代码一 1 #include bits/stdc.h2 using namespace std;3 typedef long long ll;4 #define mem(a) memset(a,0,sizeof(a))5 #define mp(x,y) make_pair(x,y)6 const int INF 0x3f3f3f3f;7 const ll INFLL 0x3f3f3f3f3f3f3f3fLL;8 inline ll read(){9 ll x0,f1;char chgetchar();
10 while(ch0||ch9){if(ch-)f-1;chgetchar();}
11 while(ch0ch9){xx*10ch-0;chgetchar();}
12 return x*f;
13 }
14 //
15 const int maxn 1e310;
16
17 int n;
18 ll a[maxn];
19 int dp[maxn][110],full;
20
21 int nx(int p,int st){
22 if(n-(p1) 9) return (19) | (st1);
23 else return st1;
24 }
25
26 int dfs(int p,int st){
27 if(p n) return st0;
28 if(dp[p][st] ! -1) return dp[p][st];
29 dp[p][st] 0; // 二维 表示在p这个位置[保证可以记忆化不被覆盖] 从p开始的10个数字的状态为st时是否可消
30
31 if((st1) 0) dp[p][st] dfs(p1,nx(p,st));
32 else{
33 int cnt 0;
34 for(int i1; i10; i){
35 if((1i st) (1i)){
36 // if (1ist){
37 // cout aa i st (1ist) endl;
38 cnt;
39 if(cnt 5) break;
40 if(a[p] a[pi]){
41 int newst st ~(1i) ~1;
42 if(dfs(p1,nx(p,newst))){
43 dp[p][st] 1;
44 break;
45 }
46 }
47 }
48 }
49 }
50 return dp[p][st];
51 }
52
53 int main(){
54 while(scanf(%d,n) ! EOF){
55 memset(dp,-1,sizeof(dp));
56 for(int i1; in; i)
57 a[n-i] read();
58 full (1min(n,10)) - 1;
59
60 cout dfs(0,full) endl;
61 }
62
63 return 0;
64 } 代码二 直接dfs模拟 1 #include bits/stdc.h2 using namespace std;3 typedef long long ll;4 #define mem(a) memset(a,0,sizeof(a))5 #define mp(x,y) make_pair(x,y)6 const int INF 0x3f3f3f3f;7 const ll INFLL 0x3f3f3f3f3f3f3f3fLL;8 inline ll read(){9 ll x0,f1;char chgetchar();
10 while(ch0||ch9){if(ch-)f-1;chgetchar();}
11 while(ch0ch9){xx*10ch-0;chgetchar();}
12 return x*f;
13 }
14 //
15 const int maxn 1e310;
16 mapint,int mp;
17 mapint,int::iterator it;
18 int a[maxn],used[maxn];
19
20 int dfs(int n){
21 while(n0 used[n]) n--;
22 if(n0) return 1;
23 if(n1) return 0;
24 int i 0;
25 int j n-1;
26 while(i5){
27 if(j0) return 0;
28 if(used[j]) {
29 j--;
30 continue;
31 }
32 if(a[n] a[j]){
33 used[j] 1;
34 if(dfs(n-1)) return 1;
35 used[j] 0;
36 }
37 i;
38 j--;
39 }
40 return 0;
41 }
42
43 int main(){
44 int n;
45 while(scanf(%d,n)!EOF){
46 mp.clear();
47 mem(used);
48 for(int i1; in; i){
49 a[i] read();
50 mp[a[i]];
51 }
52
53 int flag 1;
54 for(itmp.begin(); it!mp.end(); it){
55 if(it-second % 2){
56 flag 0;
57 break;
58 }
59 }
60 if(!flag){
61 cout 0 endl;
62 continue;
63 }
64 // cout 1 endl;
65 cout dfs(n) endl;
66 }
67
68
69 return 0;
70 } 转载于:https://www.cnblogs.com/yxg123123/p/6827697.html
