星夜的蓝天

NOIP2018模拟 权王再聚首 rightkings[差分+贪心]
NOIP2018模拟 权王再聚首 rightkings[差分+贪心] 得知二维数组开反的我顿时变成了咸鱼…… e...
扫描右侧二维码阅读全文
06
2018/11

NOIP2018模拟 权王再聚首 rightkings[差分+贪心]

NOIP2018模拟 权王再聚首 rightkings[差分+贪心]

得知二维数组开反的我顿时变成了咸鱼……
emmm……我的头图为了节省流量都是压缩过的,大佬喜欢不妨拿着PID去P站找原图,如果有上一些404网站之类的需求不妨点首页的神秘链接哦!
P站id71492280

题目:

Background

时光飞逝,转眼间「第8 届王权杯权王大赛」已经结束,记者邱神也晋升为主编,两位昔
日的「权王大赢家」在如今的主编的邀请下决定再次比拼权证交易技术……

Description

冠军苏先生在过去的数年间又有了长足的进步,因此这一次比拼他打算基于他总结的一套
理论进行权证投资,以此检验理论的正确性。这场比拼将持续n 天,在这n 天中将有m 种不同
的权证供苏先生和邱先生投资。根据苏先生的理论,他的投资行为将会遵循以下的模式:

  • 1.苏先生的交易终端会自动计算出某种权证的最优持有数目。苏先生要么不持有这种权
    证,要么就会持有这种权证的最优持有数目。

  • 2.为了节省精力,苏先生在每天只会对同一种权证进行一次买入或卖出操作。

此外,由于苏先生平时的权证投资积累,他拥有大量的初始资金可供调动,因此他不需要
关心剩余资金问题(也即不会因为资金不足而无法买入权证)。
在比拼正式开始前,苏先生找来了这m 种权证在历史上连续n 天内的价格情况进行演练。
现在,苏先生想知道:假设这些价格信息是已知的,他最快能在第几天获得至少b 收益?
由于我们显然可以通过用最优持有数目和单位权证价格之积代替原价格来忽略最优持有
数目的值对结果的影响,我们可以重新表述原问题如下:

  • 给定m 种权证在连续n 天内的价格,每种权证在同一天内只能买入或卖出共计至多一次,
  • 每种权证的持有数目只能为0 或1,初始资金足够多,求获得至少b 收益的最短时间。

Format

Input

输入的第1 行包含3 个整数n,m,b,意义见题目描述。
接下来m 行,每行包含n 个整数,第i 行第j 个数描述第i 种权证在第j 天的价格。

Output

输出一行一个整数,表示获得b 收益的最短时间。如果无法获得这么多收益,输出-1。

Sample 1

Input

3 2 10
5 2 8
0 3 5

Output

3

【样例1 说明】
苏先生只需在第1 天买入第2 种权证,在第2 天买入第1 种权证,并在第3 天全部卖出
就能得到11 收益。

Sample 2

Input

3 2 10
5 2 8
0 3 3

Output

-1

Limitation

对于全部数据,有1<= n <=5000,1<=m<= 200,0<= b <=^109,0 <=权证价格<=10000。
下表中留空的位置代表该测试点在这一项目上没有特殊约定。数据范围中给出的n 的个位上的
值可以帮助你判断测试点的类型。

分析

其实一开始我并没有太多的思路,我们考虑一下如果只有一个权证的情况,那么我们肯定在前面的某天买入,当后面的某天可以赚到最多的时候卖出。为什么这么说呢?打个比方……

你去股票市场买股票,我们可以在任何时间买入,但啥时候卖出呢?我们当然想让这支股票赚到最多钱,但是如果你第i天卖出了,有可能第i+1天股票还会涨,那你这波就血亏,如果第i+1天突然跌了,那你这波就血赚,而在本题中,你拥有无数炒股人梦寐以求的能力——你知道未来股票的走势!那还不简单,随便一支股票,如果第i天以后股票有涨一段时间,哪怕是一天也好,那么你在第i天买下这支股票是只赚不亏的,因为即使股票只涨了一天,你也可以选择一天后卖掉,这样也能赚到一天的差价。而如果一只股票只跌不涨,那地主家的傻孩子才会去买嘛。如果一只股票先跌后涨,我们大可以跌到最低点的那天买入,然后在未来卖出,而先涨后跌的情况也类似,总结一下,如果把权证的走势看成一条折线,时间为x轴,价格为y轴,则我们有如下策略:

  • 我们永远可以选择在一条上升子折线的起点买入,终点卖出。挣得的钱就是终点的高度减起点的高度
  • 下降的折线对我们来说永远是亏的,我们可以不用管它。
  • 下降的最低点必定是上升的起点。

有了这些策略,我们就可以开始贪心了。考虑到第i天的操作(买入或卖出)只与i-1天有关,动态规划一定是没问题的,但是我们可以用一个更简单的做法,即考虑拆分数组,设原数组a[i],则定义 $$ c_i=a_i-a_{i-1} $$
那么,我们只要按时间顺序将拆分数组中的所有正数全部加起来,啥时候超过期望收益就啥时候结束,单权值的情况就结束了。这样一想,多权值的完全一样,只不过你之前只处理一个权证,而现在多加一个for循环处理每天的所有权证而已,同样也是啥时候超过期望收益就啥时候结束,本题就可以轻松AC掉……

#include<bits/stdc++.h>
using namespace std;
//int a[5007][207];
int a[207][5007];
//long long c[5007][207];
long long c[207][5007];
int n,m;
long long ans,b;
int main(){
    cin >> n >> m >> b;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
        a[i][0]=a[i][1];
    }
    for(int i=1;i<=m;i++)
         for(int j=1;j<=n;j++)
            c[i][j]=a[i][j]-a[i][j-1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (c[j][i]>=0){
                ans += c[j][i];
                if (ans>=b){
                    cout << i << endl;
                    return 0;
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

后话

是啊,本题思路并不难,但是我由于考试时二维数组维度开反了,神奇的只过4个点还没RE,事后望着g++编译器陷入沉思……&&

最后修改:2018 年 11 月 06 日 09 : 49 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论

召唤看板娘