二助
6分钟前

Description

奶牛想证明他们是聪明而风趣的。为此,贝西筹备了一个奶牛博览会,她已经对N头奶牛进行了面试,确定了每头奶牛的智商和情商。 贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果,所以贝西不希望出展奶牛的智商之和小于零,或情商之和小于零。满足这两个条件下,她希望出展奶牛的智商与情商之和越大越好,请帮助贝西求出这个最大值.

Input

第一行:一个整数N,表示奶牛的数量, 1 ≤ N ≤ 100 第二行到第N + 1行:第i + 1行有两个用空格分开的整数:Si和Fi,分别表示第i头奶牛的智商和情商, -1000 ≤ Si ≤ 1000, -1000 ≤ Fi ≤ 1000

Output

第一行:单个整数,表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览,如 果这样应该输出0

Sample Input

5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample Output

8

Hint

选择 1, 3, 4 号奶牛,此时智商和为-5 + 6 + 2 = 3,情商和为7 - 3 + 1 = 5。加 入 2 号奶牛可使总和提升到10,不过由于情商和变成负的了,所以是不允许的.

题解

每只牛有两种选择:参加会展和不参加会展。我们要求在智商一定的情况下情商的最大值,这其实就是01背包的模板。状态转移方程的推导如下:
第 $i$ 只奶牛不参加会展: $dp[i][j]=dp[i-1][j]$
第 $i$ 只奶牛参加会展: $dp[i][j]=dp[i-1][j-a[i].iq]+a[i].eq$
加上决策,选取上面两种情况的最大值: $dp[i][j]=\max(dp[i-1][j], dp[i-1][j-a[i].iq]+a[i].eq)$

有一些奶牛智商居然是负的,这样导致 $j-a[i].iq$ 比 $j$ 大,可以在动规的时候判断一下,如果这只奶牛很傻,那么正着dp,否则反着dp。

因为 $a[i].iq$ 和 $a[i].eq$ 都有可能是负数,所以会导致数组越界。这时,我们可以把 $dp$ 数组向右移动 $400000$ 位。数组的改变意味着我们状态的定义也会发生改变:
$dp[j]$ 表示在奶牛智商之和为 $j-400000$ 时,情商的最大值。

但是在最后求答案时,不要忘记我们求得其实是 $dp[j]+j-400000$的最大值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

int f[1000*400*2+10];
int a[410];
int b[410];
int n;

int main()
{
    cin>>n;
    int base=1000*n;
    int upper=base*2;

    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];

    memset(f,-0x3f,sizeof f);
    f[base]=0;

    for(int i=1;i<=n;i++)
        if(a[i] >= 0)
        {
            for(int j=upper;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
        else
        {
            for(int j=0;j-a[i]<=upper;j++)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }

    int res=-upper;
    for(int i=base;i<=upper;i++)
        if(f[i]>0)
            res=max(res,f[i]+i-base);

    if(res < 0) res=0;
    cout<<res<<endl;
   // system("pause");
}



SmallK
41分钟前

题目描述

y总的这道题解的的太巧妙了,看了好长时间脑壳疼,虽然能做出来,但思路依然不通畅,我等凡人还是理解力差了点Q.Q
现在给出我的解法,希望能帮到在这里感到困惑的同学

思考过程:
首先preorder的第一个节点和postorder的最后一个节点一定是根节点root。preorder的第二个节点preorder[2]要么是左子树根节点,要么是右子树根节点(当左子树不存在);postorder的倒数第二个节点postorder[-2]要么是右子树根节点,要么是左子树根节点(当右子树不存在)。

1. 如果preorder[2]!=postorder[-2],那就说明preorder[2]和postorder[-2]所代表地根节点不是同一棵树,因此存在左子树和右子树,从而preorder[2]是左子树根节点,postorder[-2]是右子树根节点。
2. 如果preorder[2]==postorder[-2],那么就说明只存在一边的子树,那么这个时候你思考一下,其实是只有左子树也可以,只有右子树也可以。所以,存在不同的树的根源就在于这里。

那么我们就可以递归地去判断,只要存在一次preorder[2] == postorder[-2],就说明有多个解,这个时候我们只构造左子树(或右子树)就行了。


所以其实我们可以看出一个规律:只有满二叉树才能通过前序遍历和后序遍历唯一确定

算法思路:
先通过前序遍历和后序遍历的序列来构造二叉树,如果存在在不同的选择,默认选择构造左子树。最后进行中序遍历

样例

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 40;
int l[N],r[N];  //l[i],r[i]代表i号节点的左右儿子
int post[N], pre[N]; //后续遍历和前序遍历的序列
bool is_only = true;  //全局变量,是否为唯一二叉树的标志
int in[N], cnt = 0;

//根据pre[l1,r1], post[l2,r2]创建二叉树节点,并分配左右儿子指针
int build(int l1, int r1, int l2, int r2)
{
    int root = pre[l1];

    if(l1 == r1) return root;
    //根据pre[l1+1] 和 post[r2-1]来判断答案是否为1
    if(pre[l1+1] == post[r2-1]) //说明答案不唯一,我们直接认为右儿子不存在即可
        l[root] = build(l1+1, r1, l2, r2-1), is_only = false;
    else  //不相同,那么说明 pre[l1+1]为左儿子的根节点, post[r2-1]为右儿子根节点
    {
        int lpre, rpost; //lpre代表前序序列中左子树的右边界,rpost代表后序序列中右子树的左边界
        for(lpre = l1+1;lpre<=r1;lpre++) if(pre[lpre] == post[r2-1]) break;
        for(rpost = r2-1;rpost>=l2;rpost--) if(post[rpost] == pre[l1+1]) break;
        lpre--, rpost++;
        l[root] = build(l1+1, lpre, l2, rpost-1);
        r[root] = build(lpre+1, r1, rpost, r2-1);
    }

    return root;
}

//中序遍历
void inorder(int root)
{
    if(l[root] != -1) inorder(l[root]);
    in[cnt++] = root;
    if(r[root] != -1) inorder(r[root]);
}

int main()
{
    //用-1来来代表儿子节点为空
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> pre[i];
    for(int i=0;i<n;i++)
        cin >> post[i];

    //根据前序遍历和后序遍历创建二叉树
    int root = build(0,n-1,0,n-1);

    if(is_only) puts("Yes");
    else puts("No");
    inorder(root);

    cout << in[0];
    for(int i=1;i<n;i++)
        cout << " " <<in[i];
}


新鲜事 原文

cht
47分钟前
作业好多,好累


新鲜事 原文

Chunsheng
50分钟前
好饿,还没吃饭


新鲜事 原文

Ker
1小时前
新鲜事:不想学习


新鲜事 原文

Zen
1小时前
### 不知道618课程会不会打折


新鲜事 原文

loser_five
1小时前
如何才能不失败



gongcharlie
1小时前

什么鬼.PNG
代码:


int a[100000];
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {

        for(int i=0;i<target.size();i++){
            a[target[i]]++;
        }
        for(int i=0;i<arr.size();i++){
            a[arr[i]]--;
        }
        for(int i=1;i<=1001;i++){
            if(a[i]!=0) return false;
        }
        return true;
    }
};

题目:https://leetcode-cn.com/problems/make-two-arrays-equal-by-reversing-sub-arrays/submissions/




xanxus1111
2小时前
#1到n中与n互质的个数
#欧拉公式 = n(1-1/p1)(1-1/p2)...(1-1/pk)
#容质原理
#1 从1~n中去掉p1,p2,...pk的所有倍数
#2 加上pi*pj的倍数
#3 减去pi*pj*pk的倍数
#...
#等于欧拉函数展开


if __name__ == '__main__':

    n = int(input())

    for i in range(n):
        x = int(input())
        res = x

        #分解质因数
        i = 2
        while i <= x//i:
            if x % i == 0:
                res = res // i * (i - 1)
                while  x % i == 0: x //= i
            i+=1

        if  x > 1 : res = res // x * (x - 1) 

        print(res)






zmy
2小时前

求y总讲的建图的视频,谢谢各位了。