菜单

poj(2184)——Cow Exhibition(01双肩包变形)

2019年8月29日 - Java

int lowbit(int i) 

poj(2184)——Cow Exhibition(01信封包变形)

实在自身想说那道题小编以为笔者自身并未深入的知道。可是后天做了一晃,先把今天的主见记录下来

标题标大意意思是:

有N头牛,每头牛都有多个s值代表智力商数值,f值代表它的风趣值。

接下来问您智力商数值和幽默值的总和值最大是有一点,当中必需确认保证智商值的和与幽默值的和为非负数。

一初始自作者想到的也是01手拿包,不过此间还应该有负值,于是本人就从未主意了。于是学习到了一个一定于把坐标平移的艺术。

因为那边有-一千到0的值,于是大家把它们统统移到左边手去,于是成为了非负值0-贰仟。

解法:

01背包。

但是要留意的是当x>=0时,我们一维试样的01马鞍包是从后往前寻觅的(前些天自己才算真的精通为何供给的是在此以前以往推,因为我们要保管前边的不会影响后边的。那句话大概某些抽象,然则大家假使从日前以往头更新的话,那么前边dp得到的值就能够爆发再度叠合的景观,想想二维的情势或许就足以知晓,dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])
,当前地方的dp是由上一行的dp以及充裕自身的这种情景而得出的,所以是倒着找找)

当x<0时,那时大家要正着for,因为x<0时,约等于它是在负轴上的,也正是它不取x(x在此处是负值),那么就改成了dp[i-x]+y,正是一定于去前边的数,也正是为了确定保障前面前遭受眼下不产生影响。其实本身个人的主见是把它当作与x轴正方向相对称的,那样就是以前未来查询了。

 

还应该有对于dp的开头化,这里dp[10000]=0,因为它一定于是坐标原点,要往两侧增添,所以开始化为0.

 

#include
#include
#include
#include
#include
using namespace std;
#define maxn 200000
#define inf 99999999
int dp[maxn];
int main(){
 int n;
 scanf(%d,&n);
 fill(dp,dp+maxn+1,-inf);
 dp[100000]=0;
 for(int i=0;i=0){
   for(int j=maxn;j>=x;j--){
    dp[j]=max(dp[j],dp[j-x]+y);
   }
  }
  else{
   for(int j=0;j<=maxn+x;j++){
    dp[j]=max(dp[j],dp[j-x]+y);
   }
  }
 }
 int res=-inf;
 for(int i=100000;i<=maxn;i++){  //因为我们要使smart也是非负的,所以要在右半轴上找; 
  if(dp[i]>=0)   //dp[i]>=0我们要保证的是fun值也是非负的; 
  res=max(res,dp[i]+i-100000);
 }
 if(res<0) printf(0
);
 else printf(%d
,res);
}

 

 

http://www.bkjia.com/cjjc/1042313.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1042313.htmlTechArticlepoj(2184)——Cow Exhibition(01公文包变形)
其实本身想说那道题笔者认为自家自个儿并不曾深远的了然。不过后天做了须臾间,先把未来的主张记录下来
。…

        { 

For each test case, output one line containing n space-separated
integers, the i-th of which specifying the number of cows that are
stronger than cowi.

Output

    return sum; 

3 4

                val[a[i].id] = val[a[i-1].id];     
//该值等于上贰个的值

            a[i].x++; a[i].y++; //x与y都有希望为0,所以都++ 

 

Description

 

    int x, y, id; 

        sum += b[i]; 

        for(i = 0; i < n; i++) 

        update(a[0].x, 1); 

    while(scanf(“%d”, &n), n) 

void update(int i, int x) 

       还大概有有个别忘了,这题也是供给离散化的,离散化很要紧很强劲!!!

        printf(“\n”); 

 

 

    } 

    { 

    return 0; 

            a[i].id = i; 

    while(i > 0) 

        memset(val, 0, sizeof(val)); 

        sort(a, a+n, cmp1); 

}a[100005]; 

        { 

Farmer John has N cows (we number the cows from 1 to N). Each of Farmer
John’s N cows has a range of clover that she particularly likes (these
ranges might overlap). The ranges are defined by a closed interval
[S,E].

         
标题大体:给您多多线段的头S和尾E,问每一条线段中含有了略微个线段,(S和E同样不计在内)。那题先一看,完全不知晓怎么点子,认为优异的难办。

        } 

For each test case, the first line is an integer N (1 <= N <=
105), which is the number of cows. Then come N lines, the i-th of which
contains two integers: S and E(0 <= S < E <= 105) specifying
the start end location respectively of a range preferred by some cow.
Locations are given as distance from the start of the ridge.

 

Cpp代码

        i += lowbit(i); 

    return a.x < b.x;   //y一样,x由小到大排

            else val[a[i].id] = sum(a[i].x); 

        memset(b, 0, sizeof(b)); 

       就好像此!走过路过不要错失!!!

    if(a.y != b.y) return a.y > b.y;    //先由大到小排y 

Time Limit: 3000MS          Memory Limit: 65536K

 

    } 

Sample Output

    } 

 

#include <algorithm> 

Total Submissions: 6854     Accepted: 2211

#include <iostream> 

Sample Input

        val[a[0].id] = sum(a[0].x); //val[]意味着各点的sum() 

    { 

For each cow, how many cows are stronger than her? Farmer John needs
your help!

        } 

http://www.bkjia.com/Cyy/492477.htmlwww.bkjia.comtruehttp://www.bkjia.com/Cyy/492477.htmlTechArticleCows Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 6854 Accepted: 2211 Description Farmer Johns cows
have discovered that the clover growing along the ridge of the
hil…

}   

bool cmp1(node a, node b)   //排序相当重大!!!

代码:

 

    int sum = 0; 

            if(a[i].x == a[i-1].x && a[i].y == a[i-1].y) 
//若两区间相等

The input contains multiple test cases.

 

            printf(” %d”, val[i]); 

Input

        printf(“%d”, val[0]); 

但是!树状数组能够轻巧化解那么些难点!!!首先,将他们线段的s和e当做是(s,e)三个点,这样子把富有一点画出来,你就能够意识一个很神奇的光景,标题供给就能够成为:问每一个点的左上角有多少个点?

int sum(int i) 

            scanf(“%d %d”, &a[i].x, &a[i].y); 

    return i&(-i); 

The end of the input contains a single 0.

 

        for(i = 1; i < n; i++) 

 链接:http://poj.org/problem?id=2481

1 0 0

    while(i <= 100005) 

0 3

    int i; 

         
stars那题是问左下角有多少个点,而那题是问左上角,並且点不是有序排好的,所以某些不一样,特殊管理一下就足以。

But some cows are strong and some are weak. Given two cows: cowi and
cowj, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si
<= Sj and Ej <= Ei and Ei – Si > Ej – Sj, we say that cowi is
stronger than cowj.

0

 

using namespace std; 

1 2

#include <memory.h> 

            update(a[i].x, 1);          //更新该点x值

Farmer John’s cows have discovered that the clover growing along the
ridge of the hill (which we can think of as a one-dimensional number
line) in his field is particularly good.

3

        b[i] += x; 

    { 

#include <stdio.h> 

        } 

 

int n, b[100005], val[100005]; 

        { 

      
若是符合规律做,这一个y是比比皆是的,所以sum和update那么些样子就能相反了,那几个实际没什么所谓,同样的,排序的时候先y由大到小排,y一样期x由小到大排,那样小小的管理,就成为stars那题了!!!

 

Cows

        for(i = 1; i < n; i++) 

      !!!那样不就和那题最简便的stars同样呢???!!!

        i -= lowbit(i); 

int main() 

struct node 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图