首页 > 其他分享 >E - Maximum Glutton

E - Maximum Glutton

时间:2024-07-28 12:28:13浏览次数:9  
标签:int Maximum long -- Glutton 100 dp

原题链接

题解

暴力:二进制表示所有状态

为了减少重复运算:设计一个数组,代表 \(x\) 为某值的时候最小的 \(y\)

但是还需要知道吃了多少个:再加一层状态不就好了

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=1e9;

int a[100],b[100];
int dp[100][10006];

void solve()
{
    int n,x,y;
    cin>>n>>x>>y;

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

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=x;j++) dp[i][j]=inf;
    }

    dp[0][0]=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j>=1;j--)
        {
            for(int k=x;k>=a[i];k--)
            {
                dp[j][k]=min(dp[j-1][k-a[i]]+b[i],dp[j][k]);
                if(dp[j][k]<=y) ans=max(ans,j);

            }
        }
    }

    cout<<min(n,ans+1);
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}


标签:int,Maximum,long,--,Glutton,100,dp
From: https://www.cnblogs.com/pure4knowledge/p/18328098

相关文章

  • CF843E Maximum Flow
    考虑到最小割一定是满流,此时最小割边数就是答案。对于\(g_i=0\),连接\((u_i,v_i,inf)\),没有流量则一定可以走到,还需要防止隔断;对于\(g_i=1\),连接\((u_i,v_i,1),(v_i,u_i,inf)\),该边有流量则反向边一定有残余容量,且如果没满流,那么\(u_i\)可以到达\(v_i\),否则就选择它假如最......
  • 为何生成静态页的时候或者上传附件过程中有报错:Maximum execution time of 30 seconds
    错误记录:为何生成静态页的时候或者上传附件过程中有报错:Maximumexecutiontimeof30secondsexceeded 解决方案:由于上传或者生成静态页的时候执行时间太久,超过服务器超时时间限制所致:请到服务器里面PHP配置修改下超时时间即可解决(修改后需重启服务或者服务器)具体方法为:......
  • NMS(non maximum suppression)非极大值抑制
    参考学习:算法精讲-预测阶段后处理-NMS非极大值抑制_哔哩哔哩_bilibili以YOLOv1的模型来讲,预测阶段后处理就是把每个boundingbox中的每个种类的值算出全概率,再对比boundingbox中同种类物品,先设定一个阈值,把boundingbox中同种类全概率低于阈值的算为0,再进行一次降序排序,通过遍历......
  • D. Maximum Sum of Products
    链接https://codeforces.com/problemset/problem/1519/D题目分析总的来说不算难的一道题,主要是敢写就行,控制在O(n^2),枚举中心点,分成两类:一类是奇数,一类是偶数对称就行。代码#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<vector>#include<algorithm>#in......
  • F. Minimum Maximum Distance
    原题链接题解1.假设有一个以标记点\(c\)为根的子树,且子树内没有其他标记点,易得该子树内所有点的\(f\leqf(c)\),所以我们可以把该子树内的非标记点全部删掉2.完成步骤1之后,图就变成了所有叶子节点均为标记点的树3.题目等价于求该树内,最小的点到边界的最大值,也就是求树的直径......
  • The field file exceeds its maximum permitted size of 1048576 bytes
    问题—基于Springboot项目,文件上传功能报错Causedby:Thefieldfileexceedsitsmaximumpermittedsizeof1048576bytes.文件的大小超出了允许的范围。错误原因SpringBoot内嵌的Tomcat默认的所有上传的文件大小为1MB,超出这个大小就会报错,解决这个问题需要更改以下......
  • 718-Maximum length of repeated subarry
    题目描述链接:https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/Giventwointegerarrays nums1 and nums2,return themaximumlengthofasubarraythatappearsin both arrays.解释:给定两个数组nums1和nums2,求两个数组的最长公......
  • CF1973F Maximum GCD Sum Queries 题解
    题目链接点击打开链接题目解法首先想到枚举两个数列的$\gcd$,求最小代价两个数列的\(\gcd\)应该分别是\(a_1,b_1\)的因数或\(b_1,a_1\)的因数这样就把枚举范围缩小到了\(d(a_1)\timesd(b_1)\),这求最小代价需要\(O(n)\),不够快假设枚举的\(\gcd\)分别为\(x,y\)......
  • 152- Maximum Produce Subarray-最大子数组之乘积
    问题描述Givenanintegerarray nums,finda subarray.thathasthelargestproduct,andreturn theproduct.Thetestcasesaregeneratedsothattheanswerwillfitina 32-bit integer.解释:找出一个数组中乘积最大的子数组,返回子数组的乘积。案例:Input......
  • LeetCode 1353. Maximum Number of Events That Can Be Attended
    原题链接在这里:https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/description/题目:Youaregivenanarrayof events where events[i]=[startDayi,endDayi].Everyevent i startsat startDayi andendsat endDayi.Youcanattend......