洛谷 P1910 【L国的战斗之间谍】

2019/7/22 18:42:08 人评论 次浏览 分类:学习教程

话说我没想明白为什么前面有题解什么解释都没有为什么能上。。。。。。下面部分废话

其实这题是背包,三重循环的复杂度最多只有100000000(一亿)次,因为1≤n≤100,1≤m≤1000, 1≤x≤1000

数据还是很水的 不过洛谷能过有点惊讶要是我家电脑也能做到就好了

今年夏令营曾经由一位老师说:

CCF的电脑换了,换成i7了 这相信大家都知道

但!

他说CCF的评测机现在每秒能跑

400000000

(四亿)次!!!

所以大家放心写暴力骗分

虽然我不知道是不是一次只跑一个人的程序

好了废话结束

二维背包,就是同时有两个限制条件,比如原来只有重量和价值,但是现在有重量,价格和价值

再原来的基础上再加一维(一维基础上加或者二维基础上加)

然后公式改一下就行了

可以去看一下 原文是CSDN,因为背包讲了很多,二维背包放在了中间部分,不方便翻阅,就自己剪贴了一下(复制CDSDN的东西好麻烦啊)

#include<iostream>
using namespace std; 
int n,m,x;
int a[107],b[107],c[107];
int f[1007][1007];//这里用的是二维,即把原来的一维改成了二维
int main()
{
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++)//不变
    for(int j=m;j>=b[i];j--)
    for(int k=x;k>=c[i];k--)//变成两重循环(因为两个代价嘛)
        f[j][k]=max(f[j][k],f[j-b[i]][k-c[i]]+a[i]);
        //这里也变成两种代价分别减去
    cout<<f[m][x];//相应变化
    return 0;
}

上一篇:数据结构与算法

下一篇:Map集合

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->