思路:
传统的dp:
dp[i][j] 表示到第i个位置为止,分成j段的最大值
dp[i][j] = max(dp[l][j-1] + (sum[i] - sum[l]) % p) 0<= l < i
优化的dp:
我们发现n很大,但是p很小
于是
dp[i][j] 表示sum取模p后为i,分成j段的最大值
dp[i][j] = max(dp[l][j-1] + (sum[i] - l) % p) 0<= l < p
代码:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a)) const int N = 2e4 + ;
const int INF = 0x3f3f3f3f;
int dp[][], a[N];
int main() {
int n, p, k;
scanf("%d%d%d", &n, &k, &p);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
a[i] += a[i-];
a[i] %= p;
}
for (int i = ; i < p; i++) {
for (int j = ; j <= k; j++)
dp[i][j] = -INF;
}
dp[][] = ;
for (int i = ; i <= n; i++) {
for (int j = k; j >= ; j--) {
for(int l = ; l < p; l ++)
dp[a[i]][j] = max(dp[a[i]][j], dp[l][j-] + ((a[i]-l)%p+p)%p);
}
}
printf("%d\n",dp[a[n]][k]);
return ;
}
Codefroces 958C2 - Encryption (medium)的更多相关文章
-
Codefroces 958C2 - Encryption (medium) 区间dp
转自:https://www.cnblogs.com/widsom/p/8857777.html 略有修改 题目大意: n个数,划分为k段,每一段的和mod p,求出每一段的并相加,求最大是多 ...
-
[Codeforces958C2]Encryption (medium)(区间DP)
Description 题目链接 Solution 显然的区间DP,正常想法f[i][j]表示前i个数分成j块,每次在i前找一个k使得balala,然而常规打法会超时 我们发现,对于i前面的所有点,他 ...
-
20190708三人开黑CF模拟赛
7月8号晚上8点和两位巨佬开了一场虚拟cf: [Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)] 我这么蔡,只A ...
-
Dynamics CRM 2015-Data Encryption激活报错
在CRM的日常开发中,Data Encryption经常是不得不开启的一个功能.但是有时,我们可能遇到一种情况,Organization导入之后,查看Data Encryption是已激活的状态,但是 ...
-
backup, file manipulation operations (such as ALTER DATABASE ADD FILE) and encryption changes on a database must be serialized.
昨天在检查YourSQLDba备份时,发现有台数据库做备份时出现了下面错误信息,如下所示: <Exec> <ctx>yMaint.ShrinkLog</ctx> ...
-
SQL Server 2014 Backup Encryption
转载自: Microsoft MVP Award Program Blog 来源:Microsoft MVP Award Program Blog 的博客:https://blogs.msdn.mic ...
-
XShell 无法匹配的outgoing encryption算法 ,No matching outgoing encryption algorithm found
在链接的属性(SSH -> 安全性) 的加密算法列表中选择 aes256-ctr, mac加密列表中选择hmac-sha2-256,保存即可 To enable hmac-sha2-256 an ...
-
SQL Server安全(9/11):透明数据加密(Transparent Data Encryption)
在保密你的服务器和数据,防备当前复杂的攻击,SQL Server有你需要的一切.但在你能有效使用这些安全功能前,你需要理解你面对的威胁和一些基本的安全概念.这篇文章提供了基础,因此你可以对SQL Se ...
-
SQL Server安全(8/11):数据加密(Data Encryption)
在保密你的服务器和数据,防备当前复杂的攻击,SQL Server有你需要的一切.但在你能有效使用这些安全功能前,你需要理解你面对的威胁和一些基本的安全概念.这篇文章提供了基础,因此你可以对SQL Se ...
随机推荐
-
EA(企业架构)落地之道
随着业务和IT的不断融合,企业业务.信息系统和技术结合日益紧密,企业对信息系统及技术的敏捷性要求越来越高.如何在多变的环境下快速创新产品或服务并推向市场是企业面临的日益紧迫的压力.企业架构作为连接和匹 ...
-
gRaphael——JavaScript 矢量图表库:两行代码实现精美图表
gRaphael 是一个致力于帮助开发人员在网页中绘制各种精美图表的 Javascript 库,基于强大的 Raphael 矢量图形库.你只需要编写几行简单的代码就能创建出精美的条形图.饼图.点图和曲 ...
-
✡ leetcode 157. Read N Characters Given Read4 利用read4实现read --------- java
The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actu ...
-
Tomcat 配置 HTTPS双向认证
Tomcat 配置 HTTPS 双向认证指引说明: � 本文档仅提供 Linux 操作系统下的指引 � 在阅读本指引前请您在 Linux 部署 JDK 和 Tomcatserver为了 Tomcat ...
-
在eclipse中部署发布web项目 和 更改eclipseweb项目发布的路径
我的工作空间:d:workspaceweb项目名称:xxx在eclipse配置完tomcat后,发布到的路径是 d:\workspace\.metadata\.plugins\org.eclipse. ...
-
PYTHON WEATHER
小玩一下python强大的库文件,调api获取天气情况 #coding:utf-8 import urllib import json content = urllib.urlopen('http:/ ...
-
【stanford C++】字符串(String)与流(Stream)
字符串(String)与流(Stream) 一.C++中字符串(String) 字符串(String):就是(可能是空的)字符序列. C++中的字符串在概念上和Java中的字符串类似. C++字符串用 ...
-
welcome-file-list修改后不生效
用别的浏览器重新尝试一下,或者清缓存.我就是这样解决的.值得注意的就是,<welcome-file>里面指定的文件可以是.do或者是action.
-
PHP中报500错误时如何查看错误信息
在执行代码中加入下面两行代码即可 ini_set("display_errors","On"); error_reporting(E_ALL);
-
Kali2.0的简单使用--开启root用户登录
1. 安装完kali之后 2. 修改/etc/ssh/sshd_conf的文件 将: #PasswordAuthentication no 修改为: PasswordAuthentication ye ...