首页 > 其他分享 >7/22·morning

7/22·morning

时间:2023-07-22 11:12:01浏览次数:44  
标签:22 int cin long morning 1003 O2 dp

1269:【例9.13】庆功会  http://ybt.ssoier.cn:8088/problem_show.php?pid=1269

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[503],v[503],s[503];
int dp[6007];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>s[i];
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=s[i];k++){
            for(int j=m;j>=0;j--){
                if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){
                    dp[j]=dp[j-w[i]]+v[i];
                }
            }
        }
    }
    cout<<dp[m];
    return 0;
}

 


1270:【例9.14】混合背包  http://ybt.ssoier.cn:8088/problem_show.php?pid=1270

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[31],v[31],s[31];
int dp[203];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>s[i];
        if(s[i]==0)s[i]=m/w[i]+5;
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=s[i];k++){
            for(int j=m;j>=0;j--){
                if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){
                    dp[j]=dp[j-w[i]]+v[i];
                }
            }
        }
    }
    cout<<dp[m];
    return 0;
}

 


1258:【例9.2】数字金字  http://ybt.ssoier.cn:8088/problem_show.php?pid=1258

枚举10% 记忆化+递归100% dp100%

#include<bits/stdc++.h>
using namespace std;
long long R;
long long a[1003][1005];
int main(){
    cin>>R;
    for(long long i=1;i<=R;i++){
        for(long long j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    long long maxx=0;
    for(long long i=0;i<pow(2,R-1);i++){
        long long n=i;
        long long s=a[1][1],x=1;
        for(long long j=2;j<=R;j++){
            if(n%2==1)x++;
            n=n/2;
            s+=a[j][x];
        }
        maxx=max(maxx,s);
    }
    cout<<maxx;
    return 0;
}
/*
10%枚举
未通过 10分
测试点1: 答案正确 628KB 4MS
测试点2: 答案错误 768KB 9MS
测试点3: 答案错误 1012KB 7MS
测试点4: 答案错误 1536KB 8MS
测试点5: 运行超时 3548KB 995MS
测试点6: 答案错误 5160KB 55MS
测试点7: 答案错误 6248KB 78MS
测试点8: 答案错误 6772KB 125MS
测试点9: 答案错误 7476KB 101MS
测试点10: 答案错误 7500KB 101MS
*/
#include<bits/stdc++.h>
using namespace std;
int R;
int a[1003][1003];
int p[1003][1003];
int f(int n,int m){
    if(n==R){
        p[n][m]=a[n][m];
        return a[n][m];
    }
    int l1,l2; 
    if(p[n+1][m]!=0)l1=p[n+1][m];
    else l1=f(n+1,m);
    if(p[n+1][m+1]!=0)l2=p[n+1][m+1];
    else l2=f(n+1,m+1);
    p[n][m]=a[n][m]+max(l1,l2);
    return p[n][m];
}
int main(){
    cin>>R;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<f(1,1); 
    return 0;
}
/*
记忆化+递归100%
*/
#include<bits/stdc++.h>
using namespace std;
int R;
int a[1005][1005],dp[1005][1005];
int main(){
    cin>>R;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=R;i++){
        ans=max(dp[R][i],ans);
    }
    cout<<ans;
    return 0;
}
/*
dp100%
*/

 


1271:【例9.15】潜水员  http://ybt.ssoier.cn:8088/problem_show.php?pid=1271

#include<bits/stdc++.h>
using namespace std;
int m,n,k;
int O2[1003],N2[1003],w[1003];
int f[25][85];
int main(){
    cin>>m>>n;
    cin>>k;
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=k;i++){
        cin>>O2[i]>>N2[i]>>w[i];
    }
    for(int a=1;a<=k;a++){
        for(int i=m;i>=0;i--){
            for(int j=n;j>=0;j--){
                if(i>=O2[a]&&j>=N2[a])f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]);
                else if(i>=O2[a])f[i][j]=min(f[i][j],f[i-O2[a]][0]+w[a]);
                else if(j>=N2[a])f[i][j]=min(f[i][j],f[0][j-N2[a]]+w[a]);
                else f[i][j]=min(f[i][j],f[0][0]+w[a]);
            }
        }
    }
    cout<<f[m][n];
    return 0;
}
/*
f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]);
*/

标签:22,int,cin,long,morning,1003,O2,dp
From: https://www.cnblogs.com/zangqy/p/17572951.html

相关文章

  • leetcode 栈与队列 232 225
    目录基本介绍四个问题232225基本介绍栈,先进后出队列,先进先出四个问题C++中stack是容器么?我们使用的stack是属于哪个版本的STL?我们使用的STL中stack是如何实现的?stack提供迭代器来遍历stack空间么?首先大家要知道栈和队列是STL(C++标准库)里面的两个数据结构。C++标准......
  • ssh连接设置更改数据库名不起效果,连接127.0.0.1更换127.0.0.22也不报错
    ssh连接设置更改数据库名不起效果,连接127.0.0.1更换127.0.0.22也不报错 浏览器缓存清除后也一样。更换浏览器一样tomcat重启无效work目录全部删除无效myeclipse重新build工程无效重启myeclipse无效tomcat程序不指向工程下的webroot改为发布到webapp无效更换端口为8081的tomcat6无......
  • USG6395恢复登录密码和FC交换机2224console登录用户及密码
    一、USG6395恢复登录密码 CTRL+B以后需要输入的密码是Admin@huawei,password恢复出厂以后,reboot,进入console界面可以修改admin的密码,再次重启以后就可以正常网页登录了。二、FC交换机2224console的默认用户是root密码为Huawei12#$......
  • 【网络流,dp】Gym102220A Apple Business
    ProblemLink有一棵\(n\)个点的完全二叉树(点\(i\)的父亲是\(\lfloori/2\rfloor\)),第\(i\)个点有\(a_i\)个苹果。现在有\(m\)个订单,每个订单只接受\(u_i\)到\(v_i\)路径上的苹果,保证\(u_i\)是\(v_i\)的父亲,并且最多只接受\(c_i\)个苹果,单价为\(w_i\)。你可......
  • DL100 PN替换 DL100 RS422调试实例
    第一部分:现场问题描述 客户使用DL100的422通讯,需要西门子PLC使用过多422模块,PLC接入模块数量有限。换成DL100的PN通讯,使用交换机来处理。同时之前的使用中,遇到了DL100烧坏的问题。 第二部分:现场工作内容 1. 产品自身功能和参数设置体现: 接线:422通讯的接......
  • Visual Studio IDE 2022 - how to disable navigation to decompiled sources
    VisualStudioIDE2022-howtodisablenavigationtodecompiledsources ......
  • 斯坦福 CS229 机器学习中文讲义 翻译完成
    斯坦福CS229机器学习中文讲义第一部分到第三部分第四部分生成学习算法第五部分支持向量机第六部分学习理论第七部分正则化与模型选择感知器和大型边界分类器K均值聚类算法混合高斯和期望最大化算法第九部分期望最大化算法第十部分因子分析第十一部分主成分分析第十二部分......
  • [LeetCode] 2268. Minimum Number of Keypresses
    Youhaveakeypadwith 9 buttons,numberedfrom 1 to 9,eachmappedtolowercaseEnglishletters.Youcanchoosewhichcharacterseachbuttonismatchedtoaslongas:All26lowercaseEnglishlettersaremappedto.Eachcharacterismappedtoby exact......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32044近年来,我国的跨境电子商务发展迅速,在过去五年中,其贸易额增长率达到了16.2%,已经成为稳定对外贸易的一支重要力量(查看文末了解报告PDF版本免费获取方式)。点击阅读原文,获取专题报告全文,解锁文末52份跨境电商行业相关报告。一方面,随着跨境电子商......
  • P8271 [USACO22OPEN] COW Operations S 奶牛操作
    P8271[USACO22OPEN]COWOperationsS奶牛操作目录P8271[USACO22OPEN]COWOperationsS奶牛操作[USACO22OPEN]COWOperationsS题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示分析code[P8271USACO22OPEN]COWOperationsS-洛谷|计算机科学教育新生态(......