几天跟着队长做的一套题，太菜了啊，要好好努力啊
http://codeforces.com/problemset/problem/922/D
题意：
给一堆由s和h组成的字符串，让你拼接，使得子序列为“sh”的数量最多，并且输出这个最多的值
开始以为这种题是用dp写的（以前模拟训练写到有类似于：多个字符串，每个字符串可以反转，反转一次要花一定得价值，反转后会有一定得价值，问最多能有多少得价值，这题目是典型得dp，开dp[i][2]，表示前i个字符串：0表示不反转，1，表示反转的妆台得到的价值，不断转移前面的价值，最后得出答案：ans=max(dp[n][0],dp[n][1])）,但是这题，设计字符串的拼接和组合，组合多样化，并不像前面那题字符串的拼接顺序是一样的，那么观察了一下样例，好像都是s多的在前面哦，但是这样的想法是错的。s,h单关键量排序在前在后都不是正确的。然后又仔细分析了一下，如果对于一个字符串，其内部的”sh“个数是一样的，那么对于这个串的贡献=自己内部的子串+这个字符串中的h值*前面所有的s个数，然而每个自己内部的个数是固定的，交换顺序只改变相乘的部分。那么问题转化为求外部的sh串个数。那么我们随便想一想，这个串前面尽可能的多s，后面尽可能得小h，如果单单以s大排序或h小排序都不行，那么就用s/h得关键词来排序（这是一个贪心题目结构体排序中重要得一种模型）。所以随便排下序好了。坑点：当一个小块中h得个数为0时，直接设为inf
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100006;
struct node{
string s;
ll a,b;
ll num;
double val;
}s[maxn];
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100006;
struct node{
string s;
ll a,b;
ll num;
double val;
}s[maxn];
ll cmp(node a,node b){
return a.val >b.val ;
}
return a.val >b.val ;
}
int main(){
ll n;
cin>>n;
for(ll i=0;i<n;i++){
s[i].a=s[i].b=0;
cin>>s[i].s ;
s[i].num=0;
ll cnt=0;
ll size=s[i].s.size ();
for(int k=0;k<size;k++){
if(s[i].s[k]=='s'){
s[i].a++;
cnt++;
}
else{
s[i].b++;
s[i].num+=cnt;
}
}
if(s[i].b==0)s[i].val =inf;
else s[i].val=s[i].a*1.0/s[i].b;
}
sort(s,s+n,cmp);
string ss="";
ll ans=0;
ll pre=0;
for(int i=0;i<n;i++){
ss+=s[i].s;
ans+=s[i].num +s[i].b*pre;
pre+=s[i].a ;
}
printf("%lld\n",ans);
}
ll n;
cin>>n;
for(ll i=0;i<n;i++){
s[i].a=s[i].b=0;
cin>>s[i].s ;
s[i].num=0;
ll cnt=0;
ll size=s[i].s.size ();
for(int k=0;k<size;k++){
if(s[i].s[k]=='s'){
s[i].a++;
cnt++;
}
else{
s[i].b++;
s[i].num+=cnt;
}
}
if(s[i].b==0)s[i].val =inf;
else s[i].val=s[i].a*1.0/s[i].b;
}
sort(s,s+n,cmp);
string ss="";
ll ans=0;
ll pre=0;
for(int i=0;i<n;i++){
ss+=s[i].s;
ans+=s[i].num +s[i].b*pre;
pre+=s[i].a ;
}
printf("%lld\n",ans);
}
//希望自己天天都有所长进啊！！！