题意: 请用n个字符组成一个字符串使得到的权值最大，其中仅有"td","qcjjkkt","qcjjkktd"这三个字符串有权值，每包含这样一个字符串的权值是b,a,a+b。

知识点: 贪心，动态规划

思路: 因为这题的数据范围很大，直接dp会超时，然后我们可以发现这三个字符串长度为2,7,8，他们的最大公约数是56，所以我们可以做到贪心出每56个字符所贡献的最大值是多少，也就是max(8a,28b,7(a+b))，但是如果直接把前56x个字符全部枚举完之后再去动态规划剩下的字符串就会出问题，比方说

tdtdtdtd  
这是正好56个结束
假如后面还剩下3个位置
其中会出现把前面两个td删掉
换成tdtdqcjjkkt更优的情况出现

所以我们需要留一个缓冲区，也就是n%56+56，多给56个来dp就可以得到最优结果了。

其中动态规划也很好想，因为dp[i]只有4种情况，一种是他前边全是td，然后这一格什么都不用加就是最大，也就是dp[i-1]，一种他前边一格是个空的，所以你可以加个td成为最大，也就是dp[i=2]+b，接下来几种同理，dp[i-7]+a,dp[i-8]+a+b，这四种情况取最大即可。

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define endl '\n'
using namespace std;
const int m=1000000007;
int main()
{
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		ll n,a,b;
		cin >> n >> a >> b;
		ll maxn=(max(8*a,max(28*b,7*(a+b)))),x=0;
		if(maxn==8*a)
			x=(n/56-1)*8LL*a;
		else if(maxn==28*b)
			x=(n/56-1)*28LL*b;
		else
			x=(n/56-1)*7LL*(a+b);
		if(n>=56)
			n=n%56+56;
		vector<ll> dp(n+1);
		dp[0]=max(x,0LL);
		for(int i=1;i<=n;i++)
		{
			dp[i]=max(dp[i-1],dp[i]);
			if(i-2>=0)
				dp[i]=max(dp[i-2]+b,dp[i]);
			if(i-7>=0)
				dp[i]=max(dp[i-7]+a,dp[i]);
			if(i-8>=0)
				dp[i]=max(dp[i-8]+a+b,dp[i]);
		}
		cout << dp[n] << endl;
	}
	return 0;
}