F智乃的算法竞赛群友（完全背包DP+贪心）
想用背包DP，但发现n规模达到1e9。
考虑对n >= upper的部分直接用性价比最高的，n < upper的范围再进行完全背包DP。upper可以人为设定，但最好不要超过1000，因为题目未限定T个测试样例的n的和，所以可能每个样例的n都超
展开全文
题目描述
智乃加了一个算法竞赛群，她发现里面的群友个个都是人才，说话又好听。
她发现每次管理员 qcjj 在发比赛链接时，群友都会往下复读什么 qcjjkkt（清楚姐姐看看题）和 td（题单）。
现在你想要在群里发言，具体来讲，你希望使用
n 个字符组成一句话。
这句话可以视为是一个长度为
n 的字
展开全文
（该说不说，牛客娘是真的好看😋）题目如上，其实就是个分类讨论的问题，但是要注意一个点就是，有一个特殊的就是 "qcjjkktd" 可以同时包含 "qcjjkkt" 和 "td"，所以我们只需要8个字符就可以同时获得两个快乐值，非常赚，于是我兴冲冲地就把三种分类讨论直接交上去了，然后就发现忘记讨论没
展开全文
题意: 请用n个字符组成一个字符串使得到的权值最大，其中仅有"td","qcjjkkt","qcjjkktd"这三个字符串有权值，每包含这样一个字符串的权值是b,a,a+b。
知识点: 贪心，动态规划
思路: 因为这题的数据范围很大，直接dp会超时，然后我们可以发现这三个字符串长度为2,7,8，他们
展开全文
题目意思
智乃加入了一个算法竞赛群，她想要在群里用 n个字符组成一句话。这句话中每包含一个子串 "qcjjkkt"可以获得 a点快乐值，每包含一个子串 "td"可以获得 b点快乐值。子串可以重叠（例如 "qcjjkktd"同时包含 "qcjjkkt"和 "td"）。目标是最大化快乐值。
核心思路
本
展开全文
该题目总共有四种情况，第一种是qcjjkkt+qcjjkktd;第二种是td+qcjjkktd;第三种是优先qcjjkktd再加td;第四种是优先qcjjkktd再加上qcjjkkt。
#include<iostream>
using namespace std;
int main()
展开全文
题目
输入
输出
思路
设dp[i]为前i项最大的快乐值，根据题目可以发现dp[i]=max(dp[i],dp[i-1],dp[i-2]+b,dp[i-7]+a,dp[i-8]+a+b);
观察数据大小发现，n特别大时，直接暴力会超时。可以找2，7，8的最小公倍数，将n以56为一组进行贪心。
展开全文
F题 #智乃的算法竞赛群友#
题目描述
怎么排列才能最快乐？
思路
考试完没多久改出来了，我们想到只有三种情况，qcjjkkt、td和qcjjkktd，我们失败地没有注意到以n=56*k为讨论依据，想到从单位快乐值入手，但是发现会有漏洞，比如长度为8的字符，使用4个td和一个qcjjkktd哪个划算
展开全文
题目描述:
输入描述:
输出描述:
思路:
采用动态规划(dp)
分为3类:td qcjjkkt qcjjkktd 大小为2,7,8最小公倍数为56
当n极大 把大部分按照最有重复剩下用dp，当n极大分为3种全td 全qcjjkkt 全qcjjkktd取最大值
剩下部分
i-2基础上加上td
展开全文
我是把他们的公约数求出来，然后求28个td的分数，7个qsjjkktd，8个qsjjkkt，比较分数大小，有人可能觉得这样比较是不是有点草率，其实从数学是，比较的是td,qsjjkkt等模式下，每个英文字母的平均得分，所以其实很合理，然后就是动态规划，要多抽出来56个字符，因为最后一段有可能会有遗漏
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
