记录编号	392124	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.691 s
提交时间	2017-04-07 09:42:59	内存使用	179.61 MiB

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 303, MAXK = 8;
int str[MAXN];
int N, K, ch[MAXN], score[1<<MAXK];
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
LL f[MAXN][MAXN][1<<MAXK];
int len[MAXN];
inline void relax(LL &a, LL b){
  if(b > a)a = b;
}
void pre(){
  for(int i = 0; i < (1<<K); i++)scanf("%d %d", ch+i, score+i);
  for(int i = 0; i < K; i++)len[i] = i;
  for(int i = K; i <= N; i++)len[i] = len[i-K+1];
}
void solve(){
  memset(f, -0x3f, sizeof(f));
  for(int i = 0; i < N; i++)f[i][i][0] = 0;
  for(int i = 0; i < N; i++)f[i][i+1][str[i]] = 0;
  for(int w = 2; w <= N; w++){
    if(len[w] == 1){
      for(int i = 0; i+w <= N; i++){
        int j = i+w;
        for(int s = 0; s < (1<<K); s++)
          for(int l = j-1; l > i; l -= K-1)
            relax(f[i][j][s], f[i][l][s>>1]+f[l][j][s&1]);
        static LL tmp[2];
        tmp[0] = tmp[1] = -INF;
        for(int s = 0; s < (1<<K); s++)relax(tmp[ch[s]], f[i][j][s]+score[s]);
        f[i][j][0] = tmp[0], f[i][j][1] = tmp[1];
      }
    }else{
      for(int i = 0; i+w <= N; i++){
        int j = i+w;
        for(int s = 0; s < (1<<len[w]); s++)
          for(int l = j-1; l > i; l -= K-1)
            relax(f[i][j][s], f[i][l][s>>1]+f[l][j][s&1]);
      }
    }
  }
  printf("%lld\n", *max_element(f[0][N], f[0][N]+(1<<len[N])));
}
int main(){
  freopen("merge_2016.in", "r", stdin); freopen("merge_2016.out", "w", stdout);
  scanf("%d %d", &N, &K);
  for(int i = 0; i < N; i++)scanf("%1d", str+i);
  pre();
  solve();
  return 0;
}