Stone祝你元宵节快乐！

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

为了庆祝正月十五的到来，Stone 决定去采购一波汤圆。在一个 n×m 的货架上，有最多26种不同口味的 cyk 色汤圆（'a'~'z')，有的时候商家会出售三种特殊颜色的汤圆：柏皓色 ('H')，bLue***') 和金桔色 ('Q')。为了膜拜金桔，出现金桔色汤圆时，Stone 一定选择金桔色汤圆，否则一定买柏皓色或 bLue色汤圆（特殊汤圆至少买一个，如果没有特殊汤圆，Stone 就不会买汤圆）。Stone 会从货架的左上角 (1, 1) 位置开始到 (n, m) 位置取一条路径，路径上的每个汤圆都会取。Stone 的路径选择时，每一步只能向下或者向右，并且不能走出货架的范围。Stone 对不同的汤圆具有不同的喜好值，但是 Stone 假装不知道如何取才能使取得的汤圆的喜好值总和最大，你能帮助他吗？

Input

输入数据有多组（数据组数不超过 50），到 EOF 结束。

对于每组数据：

第一行为两个整数 n,m (1 <= n, m <= 1000)。第二行为 26 个整数，代表 Stone 对 cyk 系列 ('a'-'z') 汤圆的喜好值。第三行为 3 个整数，代表 Stone 对柏皓色 ('H')，bLue***') 和金桔色 ('Q') 汤圆的喜好值。接下来 n 行，每行 m 个字符（字符在一行内连续且不含空格），代表货架上该位置的汤圆类型 ('a'-'z', 'H', 'B', 'Q')。

所有汤圆喜好值的范围都为：[-1000, 1000]。

Output

每组数据输出 Stone 购买汤圆能获得的最大喜好值。如果 Stone 没有买汤圆，输出 "have to give up!!!"。

Example Input

1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1
Q
3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2
0 0 1
wQy
zab
Qma

Example Output

1
1

Hint

Author

「2017年寒假集训阶段测试赛2 - 元宵节专场」Stone

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <stack>using namespace std;typedef struct node{ int c, r;}hty;long long k[1010][1010];long long dk[1010][1010];long long dg(int c, int r, int c2, int r2)//动态规划， c， r为右下角， c2， r2为左上角{ memset(dk,0,sizeof(dk)); for(int a=c; a>=c2; a--) { for(int b=r; b>=r2; b--) { dk[a][b]=k[a][b]; if(a==c&&b==r)continue; if(b==r)dk[a][b]+=dk[a+1][b]; else if(a==c)dk[a][b]+=dk[a][b+1]; else { dk[a][b]+=max(dk[a+1][b], dk[a][b+1]); } } } return dk[c2][r2];}int main(){ int n, m; int p[60]; stack <hty> y1, y2;//y1保存Q、出现的坐标， y2保存H.B出现的坐标 while(~scanf("%d%d", &n, &m)) { while(!y1.empty()) { y1.pop(); } while(!y2.empty()) { y2.pop(); } for(int a='a'-'A'; a<='z'-'A'; a++) { scanf("%d", &p[a]); } scanf("%d%d%d%*c", &p['H'-'A'], &p['B'-'A'], &p['Q'-'A']); hty l; for(int a=0; a<n; a++) { char str[1010]; scanf("%s", str); for(int b=0; b<m; b++) { char ch=str[b]; k[a][b]=p[ch-'A'];//将字母矩阵转化为数字矩阵 if(ch=='Q') { l.c=a; l.r=b; y1.push(l); } else if(ch=='H'||ch=='B') { l.c=a; l.r=b; y2.push(l); } } getchar(); } long long maxx=-(1<<12);//最终结果 if(y1.empty()&&y2.empty())//Q与H， B 都没有出现 { printf("have to give up!!!\n"); continue; } else if(!y1.empty())//出现了Q { while(!y1.empty()) { l=y1.top(); y1.pop(); long long sum1=dg(n-1, m-1, l.c, l.r);//两次动态规划 long long sum2=dg(l.c, l.r, 0, 0); long long sum3=sum1+sum2-k[l.c][l.r];//删去重复点 if(sum3>maxx)maxx=sum3; } } else//出现了H B { while(!y2.empty()) { l=y2.top(); y2.pop(); long long sum1=dg(n-1, m-1, l.c, l.r); long long sum2=dg(l.c, l.r, 0, 0); long long sum3=sum1+sum2-k[l.c][l.r]; if(sum3>maxx)maxx=sum3; } } printf("%lld\n", maxx); } return 0;}/***************************************************User name: jk160508孙振强Result: AcceptedTake time: 384msTake Memory: 1724KBSubmit time: 2017-02-14 10:54:44****************************************************/