首页 > 其他分享 >线性dp

线性dp

时间:2022-10-20 23:56:29浏览次数:80  
标签:node const int cin ans 线性 dp

P1233 木棍加工 (dilworth定理)

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10;
int dp[N];
struct node{
    int l,r;
}a[N];
bool cmp(node &a,node &b){
    if(a.l!=b.l)return a.l>b.l;
    return a.r>b.r;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i].r>a[j].r){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans+1<<endl;
}

Dynasty Puzzles

#include<bits/stdc++.h>
using namespace std;
const int N=50;
int dp[N][N];
int main(){
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        int len=s.length();
        int beginn=s[0]-'a';
        int endd=s[len-1]-'a';
        for(int i=0;i<26;i++){
            if(dp[i][beginn]||i==beginn){
                dp[i][endd]=max(dp[i][beginn]+len,dp[i][endd]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<26;i++){
        ans=max(ans,dp[i][i]);
    }
    cout<<ans<<endl;
}

CF933A A Twisty Movement

 

 

 

 

标签:node,const,int,cin,ans,线性,dp
From: https://www.cnblogs.com/Dengpc/p/16812010.html

相关文章

  • 论文解读(FedPCL)《Federated Learning from Pre-Trained Models: A Contrastive Learni
    论文信息论文标题:FederatedLearningfromPre-TrainedModels:AContrastiveLearningApproach论文作者:YueTan,GuodongLong,JieMa,LuLiu,TianyiZhou,JingJ......
  • 记录|在WordPress设立HTTPS
    TL;DR:根据HTTPSforWordPress–WordPress.orgForums上的指示操作即可。获取HTTPS证书到Certbot上去,填MyHTTPwebsiteisrunning[Nginx]on[Ubuntu20]......
  • 经典分类:线性判别分析模型!
    作者:小雨姑娘,康涅狄格大学,Datawhale成员这几天看了看SVM的推导,看的是真的头疼,那就先梳理基础的线性判别分析模型,加深对SVM的理解。线性判别分析是一种线性的分类模型。线性......
  • 2020CCPC威海 C Rencontre(树形DP,期望)
    题意:有3个人,每个人有一些待选位置。就是当确定三个人确定位置u1,u2,u3后,需要找到一个位置v到三个位置的距离之和最小,现在给出u1,u2,u3的待选取值,问距离......
  • HDU2376——Average distance(思维+树形DP)
    原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2376原文:https://www.codenong.com/cs109682980/题意:给定一棵树,有边权,求树上任意两点之间距离的和的平均值。思路......
  • 【算法】基础DP
    参考资料背包九讲一、线性DP如果现在在状态i下,它上一步可能的状态是什么。上一步不同的状态依赖于什么。根据上面的分析,分析出状态和转移方程。注意:dp不一定只有......
  • 矩阵与线性方程组
    高斯消元当我们用线性方程组来理解矩阵时,我们有矩阵的高斯消元。高斯消元本质上是一系列的对矩阵的“变换”或者说“操作”,这种操作总共有三种:1)给某一整行乘上非零常数\(......
  • Sam's Numbers 矩阵快速幂优化dp
    ​​https://www.hackerrank.com/contests/hourrank-21/challenges/sams-numbers​​设dp[s][i]表示产生的总和是s的时候,结尾符是i的所有合法方案数。那么dp[s][i]可以由dp[......
  • 状压dp
    状压dp[SCOI2005]互不侵犯题目描述在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个......
  • 基于LDPC编译码的长距离SC-OFDM通信链路matlab仿真
    目录一、理论基础二、MATLAB仿真程序三、仿真结果一、理论基础VPI光通信系统模拟软件支持灵活的多速率传输系统,通过这个软件,用户可以从基本的光子元素向上层建立模型,......