【问题描述】
kotori是μ's的服装设计担当。她有一个技能，是把一块布料的颜色变成另一个颜色，消耗k点魔法值。
已知一件衣服的奇异度取决于这件衣服颜色的种类。
颜色种类为1时，奇异度为1。
颜色种类为2时，奇异度为3。
颜色种类不小于3时，奇异度为10。
一件衣服由很多块布料编织而成。kotori不能增加或减少布料数量，但可以消耗k点魔法值改变某块布料的颜色。
kotori拿到了n件衣服，她想让所有衣服奇异度的总和尽可能大，但她只有m点魔法值可供消耗。她想知道，消耗这些魔法值后，所有衣服奇异度总和最大值是多少？
【输入】
第一行三个正整数n，m，k，含义见问题描述。（1<=n<=500 1<=m,k<=1e18）
第二行有n个正整数ai，分别代表每件衣服布料的数量。（1<=ai<=500）
接下来n行，每行一个长度为ai的、仅包含大写字母的字符串，描述每件衣服布料的颜色。相同的字符意味着相同的颜色，不同字符代表不同的颜色。
【输出】
一个正整数，代表所有衣服奇异度总和的最大值。
【样例输入】
3 5 2
4 3 5
AAAA
PDD
CRCRC
【样例输出】
21
【样例描述】
只能进行2次变色。可以这样变色：
AAAA
PFD
TRCRC
总奇异度是1+10+10=21。
PS：这个是今年的校赛题，不过需要校园网才能访问。http://acm.bistu.edu.cn/acm/submit.jsp?problemID=2924&pageNo=1&pages=0
这个是贪心题，不过，要注意变化过程中种类数不得超过字符串的长度，比如，AA，字符串长度为2，奇异度为1，那只能变化一次，不能再变化了。要注意。
根据出题人兼大佬的讲解可知，先统计每个字符串不同种类字母的种类数。然后优先把种类2种变成种类3种，其次把种类1种变成种类2种、再变成种类3种。
可以建立一个二维数组 t[m][n],其中 m可以指的是字符串的长度，m最大为3，n可以是奇异度，最大为3（就是把大于等于3统一视为3）。
C++代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<set> #include<cstring> using namespace std; const int maxn = 502; int t[maxn][maxn]; int a[maxn]; typedef long long ll; int main(){ int n; ll m,k; cin>>n>>m>>k; ll g = m/k; for(int i = 0; i < n; i++){ cin>>a[i]; } set<char> s; int p,q; memset(t,0,sizeof(t)); for(int i = 0; i < n; i++){ char ch; s.clear(); for(int j = 0; j < a[i]; j++){ cin>>ch; s.insert(ch); } p = a[i] >= 3 ? 3 : a[i]; q = s.size() >= 3 ? 3 : s.size(); t[p][q]++; } if(g){ while(t[3][2] > 0){ t[3][2]--; t[3][3]++; g--; if(g == 0) break; } } if(g){ while(t[3][1] > 0){ t[3][1]--; t[3][2]++; g--; if(g == 0) break; t[3][2]--; t[3][3]++; g--; if(g == 0) break; } } if(g){ while(t[2][1] > 0){ t[2][1]--; t[2][2]++; g--; if(g == 0) break; } } ll sum = 0; for(int i = 1; i <= 3; i++){ sum = sum + t[i][1] + t[i][2]*3 + t[i][3]*10; } printf("%lld\n",sum); return 0; }
转载于:https://www.cnblogs.com/Weixu-Liu/p/10887215.html
相关资源：JAVA上百实例源码以及开源项目