pku 2148 Cow Exhibition

2023-10-30 10:49
文章标签 cow pku exhibition 2148

本文主要是介绍pku 2148 Cow Exhibition,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2184 Cow Exhibition 0-1背包问题变形,选定一个值作状态后,另一值可被标识。如果有更多信息需记录(信息量-1)的数组应该可以的。http://acm.pku.edu.cn/JudgeOnline/problem?id=1717 Dominos这道题也是一道类似的题目,
还可以用搜索来做。把有利的值统统加入,同时记下可能使不符合的元素,做一次排除,找到正确的最优值。 

0-1背包有时(分堆)可以用随机贪心来做的,大致思路是从多的一堆中随机一个放入少的一堆中。

 

#include  < iostream >
#define  N 101
using   namespace  std;

int  f[N],s[N];
int  n,num;
int  total;
int  tF,tS;

int  findProper( int  a, int  b, int  idx)
{
    
if  (a >= 0   &&  b >= 0 )
    {
        
if  (a  +  b  > total)
            total 
=  a  +  b;
        
return  a + b;
    }
    
if  (idx >= num  ||  a  +  b  <  total)
        
return   0 ;
    
int  i  =  findProper(a,b,idx + 1 );
    
int  j  =  findProper(a + f[idx],b + s[idx],idx + 1 );
    
return  max(i,j);
}

int  main()
{
    
int  i;
    scanf(
" %d " , & n);
    total 
=  tF  =  tS  =  num  =   0 ;

    
int  a,b;
    
for  (i = 0 ; i < n;  ++ i)
    {
        scanf(
" %d%d " , & a, & b);

        
if  (a >= 0   &&  b >= 0 )
        {
            total 
+=  a + b;
            tF 
+=  a;
            tS 
+=  b;
        }
        
else   if  (a  *  b  <= 0 )
        {
            
if (a  +  b  >   0 )
            {
                tF 
+=  a;
                tS 
+=  b;
                a 
=   - a;
                b 
=   - b;
            }
            f[num]
= a;
            s[num]
= b;
            
++ num;
        }
    }
    printf(
" %d " ,findProper(tF,tS, 0 ));
}

这篇关于pku 2148 Cow Exhibition的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/307390

相关文章

【POJ】3660 Cow Contest floyd(可以拓扑排序?)

Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6925 Accepted: 3792 Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating i

【POJ】3169 Layout 【HDU】3592 World Exhibition 差分约束

传送门:  【POJ】3169 Layout、【HDU】3592 World Exhibition 题目分析:我会说我只是凭直觉写的吗。。。。。。。 如果有B-A>=C形式的,则建边(B,A,-C)。 如果有B-A<=C形式的,则建边(A,B,C)。 对所有的点X,建边(X,X-1,0)。 最后跑一遍最短路。如果存在负环输出-1,如果点N不可达输出-2,否则输出点N的值(最短路径长

BFS —— POJ 3278 Catch That Cow

对应POJ题目:点击打开链接 Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 54686 Accepted: 17096 Description Farmer John has been informed of the location of a fugitive cow

USACO Section 2.3 Cow Pedigrees

题意: N个节点  深度为K  的正则二叉树  求  树有几种形态 思路: 一开始以为是数学题…  看了byvoid的题解才知道是dp… 每棵树由根节点、左子树、右子树构成  由此得状态转移  树=左子树*右子树 节点数和深度是影响答案的属性  所以令dp[i][j]表示i个节点深度在j以内的树的形态数 深度在j以内的树又两个深度在j-1以内的树和一个根节点构成 设左子树k个节

Codeforces 283. B. Cow Program记忆化搜索

output standard output Farmer John has just given the cows a program to play with! The program contains two integer variables, x and y, and performs the following operations on a sequence a1, a2, ..

【POJ3270】【Cow Sorting】

Cow Sorting Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 6411 Accepted: 2488 Description Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each

【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】

Silver Cow Party Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15522 Accepted: 7039 Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going

POJ 1985 Cow Marathon(树的直径)

题目链接 题意:给出一棵树,求出这个树的直径 解答:任选一点进行dfs,会找到一个最远点s,在以这个最远点s进行dfs,会找到一个最远点是t,那么s-t就是树的直径。 //#include<bits/stdc++.h>#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace

POJ 2184 Cow Exhibition (处理负值的01背包)

【题目链接】:click here~~ 【题意】: 题意:给定n头牛的聪明指数S和幸福指数F,如果存在S的和TS>=0与F的和TF>=0同时成立时, 输出TS与TF的和的最大值sum,否则,输出0。 【思路】:      转化问题,求s和为某个固定值时候最大的f和值,然后遍历这些所有的s和以及对应的f和值,求出总和总和最大的那个。      那么这样就是一个0-1背包问题,可以把s值理解

poj3278--Catch That Cow

Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 43680 Accepted: 13615 Description Farmer John has been informed of the location of a fugitive cow and wants to catch h