题意：给n,k,g1,g2,g3，然后给一个长度为n的只包含’.‘和‘#‘的字符串，
有三种type,
type 1：单个的’.’，贡献为g1,
type 2：两个连着的’.’，贡献为g2.
type 3：".#."，连续的点#点，贡献为g3.
求最优划分使得贡献最大，每个字符只能用于1个type。
字符串中’#'顶多出现50次。
type 1最多用n次。
思路：显然dp，一开始看错了题意以为是个垃圾题，后来发现这个题还是有点东西的。
这一开始感觉应该是个二维dp，但是第一维为字符串前i项，如果第二维为用了j个type1明显是爆了，所以就从#只有50下手，那么明显是第二维代表用了j个type3的最大贡献。但是这样dp是没法处理type 1的类型最多为k个。这时候这个dp最关键的地方就来了，平常的dp一般是直接dp的贡献，但是这个dp[i][j]是代表的前i个字符，构造了j个type 3，能最多搞出来多少type 2，这样dp的话，最后就能通过把一些type2转化为type1来得到最优，而且也能控制type1的个数不大于k。
这种dp之前见过，间接求答案，因为如果dp的贡献是ax+by,然后有一个x+y=n的隐形条件没有用到,但是如果dp的是type2，那么就可以知道x，然后根据隐形条件得到y，然后也可以求贡献，这样即可以控制x和y的大小的目的，又可以得到最终贡献，不过前提是有x+y=n的隐形条件。
ps:加粗的这一段比较抽象。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=101000;
const int INF=0x3f3f3f3f;
char s[MAX_N];
int dp[MAX_N][55];//代表前i个选了j个type3最多能选多少个type2 
int main(void){
 int n,k,g1,g2,g3,i,j;
 scanf("%d%d%d%d%d",&n,&k,&g1,&g2,&g3);
 scanf("%s",s+1);
 int m=0;
 for(i=1;i<=n;i++){
  if(s[i]=='#')
  m++;
 }
 for(i=0;i<=n;i++){
  for(j=0;j<=m;j++)
  dp[i][j]=-INF;
 }
 dp[0][0]=0;
 for(i=1;i<=n;i++){
  if(i-2>=1&&s[i]=='.'&&s[i-1]=='#'&&s[i-2]=='.'){
   dp[i][0]=dp[i-1][0];
   for(j=1;j<=m;j++)
   dp[i][j]=max(dp[i-1][j],dp[i-3][j-1]);
  }
  else if(s[i]=='#'){
   for(j=0;j<=m;j++)
   dp[i][j]=max(dp[i][j],dp[i-1][j]);
  }
  else if(s[i]=='.'){
   for(j=0;j<=m;j++)
   dp[i][j]=max(dp[i][j],dp[i-1][j]);
   if(i-1>=1&&s[i-1]=='.'){
    for(j=0;j<=m;j++)
    dp[i][j]=max(dp[i][j],dp[i-2][j]+1);
   }
  }
//  for(j=0;j<=m;j++){
//   cout<<i<<" "<<j<<" "<<dp[i][j]<<" !!!\n";
//  }
 }
 int ans=0;
 for(j=0;j<=m;j++){
  if(dp[n][j]<0)
  continue;
  int res=g3*j;
  int p=n-3*j-(m-j);//'.'的个数 
  int q=dp[n][j];
  int ks=0;
  ks=max(ks,q*g2+g1*min(k,p-2*q));
  ks=max(ks,min(k,p)*g1+min(q,(p-min(k,p))/2)*g2);
  if(min(k,p)>=1)
  ks=max(ks,(min(k,p)-1)*g1+min(q,(p-min(k,p)+1)/2)*g2);
  res+=ks;
  ans=max(ans,res);
 }
 printf("%d\n",ans);
 return 0;
}