P2577-午餐

绝地灬酷狼 2023-06-01 08:53 15阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 typedef long long ll;
     6 using namespace std;
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 struct P
    23 {
    24     int a;
    25     int b;
    26     bool operator < (P se)
    27     {
    28         return this->b > se.b;
    29     }
    30 };
    31 int N;
    32 P a[203];
    33 int dp[203][203*203];
    34 int sum[203];
    35 int main()
    36 {
    37     N = read();
    38     _for(i,1,N+1)
    39         a[i].a = read(),a[i].b = read();
    40     
    41     sort(a+1,a+1+N);
    42     
    43     _for(i,1,N+1) 
    44         sum[i] = sum[i-1]+a[i].a;
    45     memset(dp,0x3f,sizeof(dp));
    46     dp[0][0] = 0;
    47     _for(i,1,N+1)
    48         _for(j,0,sum[i])
    49         {
    50             if(j>=a[i].a)
    51                 dp[i][j] = min(dp[i][j],max(dp[i-1][j-a[i].a],j+a[i].b));
    52             dp[i][j] = min(dp[i][j],max(dp[i-1][j],sum[i]-j+a[i].b));
    53         }
    54     int ans = 0x3f3f3f3f;
    55     _for(i,0,sum[N])
    56         ans = min(ans,dp[N][i]);
    57     write(ans);
    58     return 0;
    59 }

转载于:https://www.cnblogs.com/Asurudo/p/11429548.html

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关简单模拟题——无法吃午餐的学生数量

CSDN第七期竞赛分享，为大家分享一道做过的比较有意思的简单模拟题——无法吃午餐的学生数量，希望对你有帮助~~

╰半夏微凉°/ 2024年04月22日 19:18/ 0 赞/ 38 阅读

相关【C++】*P、P 、&P的区别

在刚开始接触到C++的时候一提到指针P就会联想到一个箭头指向了一个地址，这是一个最为基础而且不算全面的理解，在后面的学习过程中总是能遇到类似指针的知识点，发现一个简单...

刺骨的言语ヽ痛彻心扉/ 2024年04月20日 00:16/ 0 赞/ 146 阅读

相关 P2577-午餐

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

绝地灬酷狼/ 2023年06月01日 08:53/ 0 赞/ 16 阅读

相关【栈】无法吃午餐的学生数量（leetcode1700）

一、题目学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治

叁歲伎倆/ 2022年10月18日 12:54/ 0 赞/ 61 阅读

相关 p++与(p++) (p)++ ++p *(++p)

<pre name="code" class="cpp">include <stdio.h> int main(void) { in

浅浅的花香味﹌/ 2022年08月27日 15:56/ 0 赞/ 233 阅读

相关没有免费的午餐定理和丑小鸭定理

没有免费的午餐定理(noerfelunhchtocerm，简称NFL)。该定理由wolpert和Macerday提出，结论是由于对所有可能函数的相互补偿，最优化算法的性能是等价

浅浅的花香味﹌/ 2022年08月21日 11:48/ 0 赞/ 121 阅读

相关 P3P

P3P是万维网联盟（W3C）公布的一项隐私保护推荐标准，旨在为网上冲浪的 Internet用户提供隐私保护。现在有越来越多的网站在消费者访问时，都会收集一些用户信息。制定P3P

冷不防/ 2022年07月10日 05:28/ 0 赞/ 210 阅读

相关【C语言】++p，p++，++p，++++p，++*p++

部分运算符优先级和结合方向表 ![这里写图片描述][SouthEast] 首先我们在优先级及结合方向表中可以看到++运算符和\运算符是同属于一级

桃扇骨/ 2022年06月17日 00:50/ 0 赞/ 269 阅读

相关 p *p **p

include<iostream> using namespace std; void test01(){ int a=10; int

布满荆棘的人生/ 2022年04月05日 13:23/ 0 赞/ 263 阅读

相关洛谷P2577 午餐

![1522713-20190818195339101-1624499565.png][] ![1522713-20190818195348919-562519419.pn

傷城~/ 2021年10月26日 13:36/ 0 赞/ 431 阅读