DP 回溯    发布于 2019-08-08   306人围观   0条评论

题目大意

给n个数,每个时刻就会有一个新的数可用,求每个时刻所有可用的数字按照序列位置组成的最长上升子序列长度。数据生成完全随机。

题解

由于数据完全随机生成,所以当所有数都可用的时候,LIS的期望长度是n1/2 。我们删掉一个数,这个数在LIS中的概率期望是1/n1/2

我们可以把原问题逆向来考虑,从一开始所有数可用,然后不断删除数字。

如果删除的数字在上一次的LIS中,则我们需要重新求一次LIS,否则就延续上一次的答案。

如果我们使用O(nlogn)方法的LIS,那么一组数据的总体时间复杂度就是O(n3/2logn)

这题因为手写二分写丑了没用lower_bound被卡T一次,然后因为行末空格被卡PE一次,AWSL。

代码


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 50005;
int T;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n;
int p[maxn],k[maxn],seq[maxn];
int ans[maxn],vis[maxn],ban[maxn],pre[maxn];
int len = 0;
int pos;
int work(){
    for(int i = 1;i <= len;++i)
        seq[i] = 0,vis[seq[i]] = 0;
    seq[0] = 0;
    len = 0;
    f
查看更多
DP 贪心 回溯    发布于 2019-07-20   309人围观   0条评论

题目大意

现在给一个n*n的矩阵,你要从(1,1)走到(n,n),求一条路径,使得路径上所有数的乘积的尾部零的个数最少。

题解

我们先考虑尾部零怎么能够产生。

首先要产生尾部零,就一定要乘10或者0。

先来考虑0的情况,如果你走一条带有0的路径的话,那么最后乘积一定会是0,尾部零的数量为1个。

如果我们不走带有0的路径的话,那么要产生尾部0就一定要有因数10,而且有多少个因数10就有多少个尾部零。

而10这个数,很明显的,我们能够将其分解为2*5,由质因数分解的唯一性,我们只需要统计路径上2和5的个数,然后取其中的最少就是最终因数10的个数,也即尾部零的个数。

讨论完尾部0的产生,我们来看一下怎样选择路径。

我们可以先不考虑带0的路径,先来看带质因数2和5的路径。

我们可以用一个三位dp[x][y][0/1]代表走到点(x,y),质因数2/5总共有几个(0和1分别表示选2和选5),然后我们转移方程是很容易写出来的。不过要注意边界,请自行看参考代码。

最后我们得到的dp[n][n][0]和dp[n][n][1]中的最小值就是不考虑带0路径的答案。这里其实是一种贪心思想,由于非常简单十分好理解不再证明(贪心的证明一般都是反证)。

然后我们要看看有没有带0的路径,因为带0的路径尾部零只有1个,所以有可能使答案更小。

我们在DP过程中分别记录选2和选5个数最少的路径(记录从哪个方向来就行了),然后最后进行回溯输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
int n;
const int maxn = 1005;
int mp[maxn][maxn];
int c;
查看更多