51nod 1182 完美字符串
超级简单的贪心算法
首先将n个字符按照字符个数进行排序，尽可能让完美度最大的话，就是让字符个数多的得到较大的完美度，就可以得到最后的最大完美度了
最优子结构:
\[i个字符的完美度=前i-1个字符完美度+当前字符最大完美度(给当前字符赋予最大的完美度)\]
贪心选择:
尽可能给字符个数较多的字符较大的完美度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include<stdio.h>
#include<string>
using namespace std;
void insert_array(int a[])
{
int tmp=0;
for(int i=1; i<26; i++)
{
int j=i;
while(j>0&&a[j]>a[j-1])
{
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
j--;
}
}
}
int main()
{
char s[10005];
scanf("%s",s);
int temp[26];
for(int i=0; i<26; i++)
temp[i]=0;
for(int i=0; s[i]!='\0'; i++)
{
if(s[i]-97>=0)
temp[s[i]-97]++;
else if(s[i]-65>=0)
temp[s[i]-65]++;
}
insert_array(temp);
int sum=0;
for(int i=26; i>=0; i--)
{
if(temp[26-i]>0)
sum+=temp[26-i]*i;
else
{
while(temp[i]==0)
i--;
}
}
cout<<sum<<endl;
}
|