51NOD 1418 放球游戏 模拟

1418 放球游戏 题目来源： TopCoder 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 收藏 关注 有N个球排成一排，每个球都是R、G、B三种颜色之一。现在想重新排列这一排球，你要重复以下过程N次： 1）从原来的那排球中的最左侧取出一个球； 2）将取出的求插入新的球排列的任意位置，即可以放在最左或最右端，也可以插入那排球的任意两个相邻球之间； 3）计算这轮得分，如果是第一个球那么得0分；如果放在两端（最左或最右端）得分为除了新放入的球外，剩余球的颜色种数；如果放在两个球之间，那么得分为这个新放入的球左侧所有球的颜色种数与这个球右侧所有球的颜色种数的和。（解释一下“颜色种数”：一堆球里出现的不同颜色个数，对应这里的得分就是一种颜色得一分，多个球同色只算一次得分。） 那么在最优操作下，最多能得到的总分是多少？ Input 多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5 每组测试数据有相同的结构构成： 每组数据一行，只有一个有‘R’，‘G’，‘B’三个字符构成的字符串S，表示原始的球排列。其中，S包含字符个数不超过50，且无空串。 Output 每组数据一行输出，即最大的总得分。 Input示例 3 RGB RGGRBBB RRRGBRR Output示例 3 21 16

感觉每次做51NOD都要脑洞大开…. 显然 每次插入一个球 都要保证插入位置2边的球颜色种类数尽可能多 假设有2个堆 考虑插入x色球 如果哪个堆没有颜色为x的球 就插进哪个堆

#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> struct C{ C()=default; bool flag[3]={0,0,0}; int score=0;//可以获得的分数(颜色种数) void add(char ch){//插入ch颜色的球 ch-='0'; score+=1; flag[ch]=true; } bool check(char ch){//检查有没有ch颜色的球 return flag[ch-'0']; } }; int slove(char*s){ int n=strlen(s); if(n<=2) return n-1; for(int i=0;i<n;++i) s[i]=s[i]=='R'?'0':s[i]=='G'?'1':'2'; C c1,c2; c1.add(s[0]),c2.add(s[1]); int ans=1; for(int i=2;i<n;++i){ ans+=c1.score+c2.score; if(!c1.check(s[i])){ c1.add(s[i]); } else if(!c2.check(s[i])){ c2.add(s[i]); } } return ans; } int main() { //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); int T; scanf("%d",&T); char s[55]; while(T--){ scanf("%s",s); printf("%d\n",slove(s)); } return 0; }