K-序列(埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛)
2024-08-30 21:03:19
题目描述
给一个数组 a,长度为 n,若某个子序列中的和为 K 的倍数,那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度,满足这个序列是 K 序列。
输入描述:
第一行为两个整数 n, K, 以空格分隔,第二行为 n 个整数,表示 a[1] ∼ a[n],1 ≤ n ≤ 10
5
, 1 ≤ a[i] ≤ 10
9
, 1 ≤ nK ≤ 10
7
输出描述:
输出一个整数表示最长子序列的长度 m
示例1
输入
7 5
10 3 4 2 2 9 8
输出
6
写的时候暴力过了,但标准解法是用dp来写的。二维K数组保存结果
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
#define ll long long
int dp[][];
int a[],n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<n;i++)
scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
dp[a[]%k][]=;
int flag=;
for(int i=;i<n;i++)
{
a[i]%=k;
flag^=;
for(int j=;j<k;j++)
{
if(dp[j][flag^])
{
dp[(j+a[i])%k][flag]=max(dp[(j+a[i])%k][flag^],dp[j][flag^]+);
}
else dp[(j+a[i])%k][flag]=dp[(j+a[i])%k][flag^];
}
}
printf("%d\n",max(dp[][],dp[][]));
return ;
}
最新文章
- python 添加tab补全
- 兼容版本实现 XMLHttpRequest
- windows apache开启url rewrite
- APPCAN MAS接口之AJAX
- MySQL服务器权限表
- log4net按照不同的级别输出到不同文件
- Java正则表达式教程
- css弹性盒子学习
- JNI c++ 调用 java
- 惠威的M200MK3的前级电子分频板
- B/S 网站技术选型
- BZOJ 1367([Baltic2004]sequence-左偏树+中位数贪心)
- double减法不准确的那些事儿
- Spark算子--countByKey
- Eclipse CDT开发环境搭建及问题记录(Windows)
- mini-tabs多个div并列,并可隐藏某个div
- 如何测试连接MsSQL数据库-------UDL文件
- Springboot+websocket+定时器实现消息推送
- 学机器学习,不会数据处理怎么行?—— 二、Pandas详解
- Jenkins安装部署(一)