首页 > 代码库 > codeforces455B - A Lot of Games DP
codeforces455B - A Lot of Games DP
题意:给你一个有重复数字的序列,每一次你选一个值,删除这个值(不删除等于这个值的其他值),然后再删除等于a[i] - 1 和 a[i] +1 的其他值,得到a[i]的价值,问你最多能得到多少价值
解题思路:其实就是一个DP,不能连续取 dp[i] = max(dp[i-1],d[i] + dp[i-2]);
解题代码:
1 // File Name: 1.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月12日 星期六 23时30分16秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<climits> 25 #include<queue> 26 27 using namespace std; 28 29 struct node{ 30 int num; 31 int ok; 32 int ok1; 33 struct node *next[30]; 34 }; 35 struct node* newnode(){ 36 struct node * p = (node *)malloc(sizeof(node)); 37 for(int i =0 ;i < 30;i ++) 38 p->next[i] = NULL; 39 p->ok = 0; 40 p->num = 0 ; 41 return p ; 42 } 43 char str[100004]; 44 int len ; 45 void build(struct node * p, int i ) 46 { 47 48 int k = str[i] -‘a‘; 49 if(i == len ) 50 return ; 51 if(p->next[k] == NULL) 52 { 53 struct node * t = newnode(); 54 t->num ++; 55 p->next[k] = t; 56 build(p->next[k],i+1); 57 } 58 else { 59 p->next[k]->num += 1; 60 build(p->next[k],i+1); 61 } 62 int tok = 0 ; 63 int nok = 0 ; 64 int t1ok = 0 ; 65 for(int i= 0;i < 30 ;i ++) 66 { 67 if(p->next[i] != NULL) 68 { 69 nok = 1; 70 if(p->next[i]->ok == 0 ) 71 tok = 1; 72 if(p->next[i]->ok1 == 1) 73 t1ok = 1; 74 } 75 } 76 if(!nok || tok) 77 p->ok = 1; 78 else p->ok = 0; 79 if(nok) 80 { 81 if(t1ok) 82 p->ok1 = 0; 83 else p->ok1 =1; 84 }else{ 85 p->ok1 = 0; 86 } 87 } 88 int ans; 89 void find(struct node * p, int i ) 90 { 91 int k = str[i] -‘a‘; 92 if(i == len ) 93 { 94 ans = p->num ; 95 return ; 96 } 97 if(p->next[k] == NULL) 98 { 99 return ; 100 }else find(p->next[k],i+1);101 }102 int main(){103 int n , k;104 105 struct node * head = newnode();106 scanf("%d %d",&n,&k);107 while(n --){108 scanf("%s",str);109 len = strlen(str);110 build(head,0);111 }112 // printf("%d %d\n",head->ok,head->ok1);113 if(head->ok)114 {115 if(!head->ok1)116 printf("First\n");117 else{118 if(k % 2 == 1)119 printf("First\n");120 else printf("Second\n");121 }122 }else{123 printf("Second\n"); 124 }125 return 0;126 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。