题目链接:传送门
题目:
题目背景 【为了响应党*勤节俭、反铺张的精神,题目背景描述故事部分略去^-^】
题目描述 给出一列数字,需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解,则输出使得最后一个数最小的同时,字典序最大的解(即先要满足最后一个数最小;如果有多组解,则使得第一个数尽量大;如果仍有多组解,则使得第二个数尽量大,依次类推……)。
输入输出格式
输入格式: 共一行,为初始的数字。 输出格式: 共一行,为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。 输入输出样例
输入样例#: [] [] [] [] [] 输出样例#: []
,,,
[]
,
[]
,,
[] []
, 说明 【题目来源】 lzn改编 【数据范围】 对于10%的数据,输入长度<= 对于30%的数据,输入长度<= 对于50%的数据,输入长度<= 对于100%的数据,输入长度<=
dp练得还是太少了呀。其实复杂dp和大模拟很像,要从每个细节考虑,逐个击破,囫囵吞枣使不得。刚开始我乍一看贪心可用,强行贪心搜索,实际上时间复杂度没考虑,很多细节也没考虑到。。。而且搜索写得还很麻烦,写完了还很多bug,加了一通乱七八糟的特判,最后还是以WA告终。。。
思路:
·第一步:
根据题意,当然要先找最小的最后一个数。本来想贪心地从后开始搜索,第一个满足条件的就是最小,但是发现遇到0的时候状况千变万化,很难控制:比如:
100 000 104 123
搜索过程中会出现以下的情况:
① 100000 > 104,不满足
② 10000 > 0104,不满足
③ 1000 > 00104,不满足
像这样,连续出现的0会导致每次搜索失败都要回到之前的位置101,而不能直接回到最后一个数123,这就导致这样搜索的时间复杂度是指数级的,不可用。
但是从后往前找又想不到什么办法记录状态,不能用dp来做,僵硬。。。
于是想到考虑一个子问题:
子串被分割成若干个严格递增的数后,使得最后一个数最小时,找到最小的最后一个数。
然后可以惊奇地发现,如果之前的所有子串都计算完了,长度+1之后可以利用之前的结果:
假设当前位置是i,如果[0, j-1]的子串的最小的最后一个数是a,那么只要a < [j, i]的子串对应的数,那么到位置i为止的最后一个数就可以是[j, i],只要从后往前枚举j,找到的第一个满足条件a < [j, i]的j,对应的[j, i]就是要找的最小的数了,时间复杂度大概是O(n2)。
不过这还没完。“如果有多组解,使得第一个数尽量大”。。。
·第二步:
我们想要找到最大第一个数,首先就要使第二个数尽量大,然后在这之前要使第三个数尽量大,再在之前就是第四个数尽量大。。。。所以考虑从后往前找,但是直接跑一遍还是会遇到刚开始的搜索的问题(多个零导致指数级时间),比如:
1234765
最后一个数最小是765,然后往前贪心的话找到的会是最大的234,但是234被用掉之后第一个只剩下1。而我们可以发现12,34,765也是满足题意的,12显然比1大,不妥QWQ。
对于每个位置的决策,不仅仅取决于右边相邻的一个位置,还取决于右边的右边,以及右边的右边的右边……的位置。于是还是要回到动态规划上面来。重复利用之前的状态:
对于每个位置j,子串[j, N]的第一个数会有一个最大值(当然是在第一步割出最小的最后一个数之后),这个最大值可以用于更新在位置j之前的所有位置i的对应子串[i, N]的第一个数的最大值。
状态&状态转移方程见代码
时间复杂度是O(n2)
#include <bits/stdc++.h> using namespace std;
const int MAX_N = ; string s;
int a[MAX_N], len;
int st[MAX_N], ed[MAX_N];
//st 开始坐标, ed 结束坐标 bool cmp(int st1, int ed1, int st2, int ed2)
{
while (st1 <= ed1 && a[st1] == )
st1++;
while (st2 <= ed2 && a[st2] == )
st2++;
int len1 = ed1 - st1 + ;
int len2 = ed2 - st2 + ;
if (len1 < len2)
return true;
if (len1 > len2)
return false;
for (int i = ; i < len1; i++) {
if (a[st1+i] < a[st2+i])
return true;
if (a[st1+i] > a[st2+i])
return false;
}
return false;
} void dp2()
{
memset(ed, , sizeof ed);
ed[st[len]] = len;
int ind = st[len]-;
while (ind >= && !a[ind])
ed[ind--] = len;
for (int i = st[len]-; i >= ; i--) {
ed[i] = max(ed[i], i);
for (int j = st[len]-; j > i; j--)
if (cmp(i, j, j+, ed[j+])) {
ed[i] = max(ed[i], j);
break;
}
}
} void dp()
{
st[] = ;
for (int i = ; i <= len; i++) {
st[i] = ;
for (int j = i; j >= ; j--)
if (cmp(st[j-], j-, j, i)) {
st[i] = j;
break;
}
}
} int main()
{
cin >> s;
len = s.size();
for (int i = ; i < len; i++)
a[i+] = s[i] - '';
dp();
dp2();
bool firstprint = true;
for (int i = ; i <= len; i++) {
if (firstprint)
firstprint = false;
else
putchar(',');
for (int j = i; j <= ed[i]; j++) {
putchar(s[j-]);
}
i = ed[i];
}
cout << endl;
return ;
}
洛谷P1415 拆分数列(dp)的更多相关文章
-
洛谷P1415 拆分数列[序列DP 状态 打印]
题目背景 [为了响应党*勤节俭.反铺张的精神,题目背景描述故事部分略去^-^] 题目描述 给出一列数字,需要你添加任意多个逗号将其拆成若干个严格递增的数.如果有多组解,则输出使得最后一个数最小的同时 ...
-
洛谷 P1415 拆分数列 解题报告
拆分数列 题目背景 [为了响应党*勤节俭.反铺张的精神,题目背景描述故事部分略去^-^] 题目描述 给出一列数字,需要你添加任意多个逗号将其拆成若干个严格递增的数. 如果有多组解,则输出使得最后一个 ...
-
洛谷P1415 拆分数列
题目背景 [为了响应党*勤节俭.反铺张的精神,题目背景描述故事部分略去^-^] 题目描述 给出一列数字,需要你添加任意多个逗号将其拆成若干个严格递增的数.如果有多组解,则输出使得最后一个数最小的同时 ...
-
洛谷P4063 [JXOI2017]数列(dp)
题意 题目链接 Sol 这题想还是不难想的,就是写起来很麻烦,然后去看了一下loj的最短代码表示只能Orz 首先不难发现一条性质:能够选择的区间一定是不断收缩的,而且新的可选区间一定是旧区间的某个位置 ...
-
P1415 拆分数列 DP
传送门: 题意: 将一个数字串分成许多不同的小串,使得这些小串代表的数字严格递增,要求最后一个数字尽可能地小. 然后满足字典序尽可能大. 思路: 由于最后一个数字要尽可能地小,所以先处理出每个数的L[ ...
-
洛谷P1108 低价购买[DP | LIS方案数]
题目描述 “低价购买”这条建议是在奶牛股票市场取得成功的一半规则.要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买:再低价购买”.每次你购买一支股票,你必须用低于你上次购买它的价格购买它 ...
-
NOIP2017提高组Day2T2 宝藏 洛谷P3959 状压dp
原文链接https://www.cnblogs.com/zhouzhendong/p/9261079.html 题目传送门 - 洛谷P3959 题目传送门 - Vijos P2032 题意 给定一个 ...
-
洛谷P1244 青蛙过河 DP/思路
又是一道奇奇怪怪的DP(其实是思路题). 原文戳>>https://www.luogu.org/problem/show?pid=1244<< 这题的意思给的挺模糊,需要一定的 ...
-
洛谷P3928 Sequence2(dp,线段树)
题目链接: 洛谷 题目大意在描述底下有.此处不赘述. 明显是个类似于LIS的dp. 令 $dp[i][j]$ 表示: $j=1$ 时表示已经处理了 $i$ 个数,上一个选的数来自序列 $A[0]$ 的 ...
随机推荐
-
nodejs 代理 解决开发环境跨域问题
前后端分离项目中,会遇到跨域问题.解决方法无非就是jsonp cors等. 本次项目前端不搭node服务,线上用nginx搭站点,nginx转发ajax请求server. 本地开发环境的跨域问题用no ...
-
剑指offer--面试题21
题目:设计包含min函数的栈,pop(),push(),min()的时间复杂度均为O(1) 自己所写代码如下:(写‘栈’的代码还是有些不熟练!) #include <iostream> u ...
-
C#使用Xamarin开发可移植移动应用(3.Xamarin.Views控件)附源码
前言 系列目录 C#使用Xamarin开发可移植移动应用目录 源码地址:https://github.com/l2999019/DemoApp 可以Star一下,随意 - - 说点什么.. .NET ...
-
jquery 第三章
1.回顾$(document).ready(function(){ })$(function(){ }) ID选择器.类选择器.元素选择器层次选择器:空格(上文下:tr td{})属性过滤 ...
-
归并排序(递归排序and外排排序)
分析: /** * 归并排序 (先将数组利用归并排序排成 有序的左边数组和右边数组,再比较左边数组和右边数组的数值大小进行排序) * */ public class MergeSort { publi ...
-
jvm感知docker容器参数
docker中的jvm检测到的是宿主机的内存信息,它无法感知容器的资源上限,这样可能会导致意外的情况. -m参数用于限制容器使用内存的大小,超过大小时会被OOMKilled. -Xmx: 默认为物理 ...
-
Kafka技术原理
详情请参见:http://zqhxuyuan.github.io/2016/05/26/2016-05-13-Kafka-Book-Sample
-
Django接收自定义http header(转)
add by zhj: Django将所有http header(包括你自定义的http header)都放在了HttpRequest.META这个Python标准字典中,当然HttpRequest. ...
-
ASN.1详解
Chapter 4 ASN.1 4.1 网络数据表示及编码4.2 ASN.1的基本概念4.3 基本编码规则 4.1 网络数据表示及编码ASN.1(Abstract Syntax Notation 1) ...
-
P2819 图的m着色问题
题目背景 给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m ...