首页 > 其他分享 >nflsoj 选数1 2 3

nflsoj 选数1 2 3

时间:2023-08-06 21:45:16浏览次数:36  
标签:const nflsoj 选法 int 选数 LL 不选 long

5711 取数-1

状态表示:1维

集合:前 \(i\) 个数里面选法和的最大值

属性:Max

状态计算:选或不选

选:\(f(i-1)+a_i\) 不选:\(f(i-1)\)

#include <iostream>
using namespace std;
const int N = 55;
int a[N],f[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=a[1];
    for(int i=2;i<=n;i++)
        f[i]=max(f[i-2]+a[i],f[i-1]);
    cout<<f[n];
    return 0;
}

5712 取数-2

状态表示:1维

集合:前 \(i\) 个数所有选法和的最大值

属性:Max

状态计算:连续选2个或不选

连续选两个:\(f(i-3)+a_{i-1}+a_i\) (注意要隔一个,不然就连起来了) 不选:\(f(i-1)\)

记得开 long long,因为 \(10^5×10^5\) 爆掉了(估算,实际上没有这么多,但是超过int的取值范围了)

#include <iostream>
using namespace std;
const int N = 1000010;
typedef long long LL;
int a[N];
LL f[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[2]=a[1]+a[2];
    for(int i=3;i<=n;i++)
        f[i]=max(f[i-1],f[i-3]+a[i-1]+a[i]);
    cout<<f[n];
    return 0;
}

5713 取数-3

状态表示:1维

集合:前 \(i\) 个数所有选法和的最大值

属性:Max

状态计算:不选,选1个,连续选2个

不选:\(f(i-1)\) 选1个:\(f(i-1)+a_i\) 选2个:\(f(i-3)+a_{i-1}+a_i\) (注意隔一个)

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 10005;
LL f[N];
LL a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=a[1];
    for(int i=2;i<=n;i++)
        f[i]=max(f[i-1],max(f[i-3]+a[i-1]+a[i],f[i-2]+a[i]));
    cout<<f[n];
    return 0;
}

标签:const,nflsoj,选法,int,选数,LL,不选,long
From: https://www.cnblogs.com/xiaozhu0602/p/17610115.html

相关文章

  • nflsoj 1351 抓住奶牛
    这题类似走迷宫,走迷宫是向四个方向进行拓展,而这道题好比是向三个方向拓展,分别是:\(x+1,x-1,x×2\)在这里拓展的时候我写了一个函数operation来计算拓展后的坐标这里判断坐标是否合法的时候我取了最大值的两倍加5,因为坐标不一定在\(k\)的左边,有可能超出去了再往回走,不过超出一......
  • nflsoj 5924 选排列
    与全排列略微有些不同,只需要将退出条件需要改成u==r#include<iostream>usingnamespacestd;constintN=15;intr,n;intpath[N];boolst[N];voiddfs(intu){if(u==r){for(inti=0;i<r;i++)printf("%d",path[i]);printf("\n&......
  • nflsoj 5926 素数环
    题目非常简单,只需要判断相邻两个数的和是不是素数,素数的判断参考数论不过要注意的一点是题目说的是一个环,所以首尾两个数的和也要是素数我在输出的时候加上了is_prime(path[n-1]+1)来判断#include<iostream>usingnamespacestd;constintN=20;intn;intpath[N];bo......
  • acwing选数异或 dp
    题目链接:https://www.acwing.com/problem/content/description/4648/题解链接[转载]:https://www.acwing.com/solution/content/137064/1#include<iostream>2#include<algorithm>3#include<vector>4#include<string>5#include<queue>......
  • [HNOI2012] 集合选数
    [HNOI2012]集合选数目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示题意概括思路历程:1.设计状态2.设计转移代码实现:题目描述《集合论与图论》这门课程有一道作业题,要求同学们求出\(\{1,2,3,4,5\}\)的所有满足以下条件的子集:若\(x\)在该子集中,则\(2......
  • Jquery遍历筛选数组的几种方法和遍历解析json对象,Map()方法详解以及数组中查询某值是
    1.jquerygrep()筛选遍历数组(可以得到反转的数组)//1.jquerygrep()筛选遍历数组(可以得到反转的数组)vararray=[1,5,9,3,12,4,48,98,4,75,2,10,11];varfilterArray=$.grep(array,(currentValue)=>{returncurrentValue>10;});console.log(`${filt......
  • 根据paentId 去删选数据
    functionparseTree(tree){constres=[]array.forEach(item=>{//如果item中有children,则递归调用item.parentId=item.parentId||0;letid=item.idletchildren=item.childrenif(children){children.forEa......
  • ExcelJS 导入导出excel带下拉框筛选数据
    importExcelJSfrom"exceljs"; asyncfunctionexportExcelTemplate(deptList:any){ constworkbook=newExcelJS.Workbook(); constworksheet=workbook.addWorksheet("模板"); worksheet.columns=[  {   header:"编号"......
  • acwing 4645. 选数异或
     输出yesnoyes no题意分析,给一串数组,再在每次提问时给出一个区间,l,r;求l,r区间内是否存在两个数,两数异或后值为给出的x;已知a^b=x-->a^x=b;思路:1,把每个数异或x,存在另一个数组(b)里,暴力搜索,看区间内b数组内数字是否有等于a数组内数字,TLE2.记录下标,比较每个......
  • odoo wizard界面显示带复选框列表及勾选数据获取
    实践环境Odoo14.0-20221212(CommunityEdition)需求描述如下图(非实际项目界面截图,仅用于介绍本文主题),打开记录详情页(form视图),点击某个按钮(图中的"选取ffers"按钮),弹出一个向导(wizard)界面,并将详情页中内联tree视图("Offers"Tab页)的列表记录展示到向导界面,且要支持复选框,用......