100分(第一个点不过）求调

B3637 最长上升子序列

A_yixiubro @ 2024-10-07 09:46:51

#include <iostream>
using namespace std;
int main(){
    int n,l,k;
    int b[5001][11];
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>b[i][1];
        b[i][2]=1;
        b[i][3]=0;
    }
    for (int i=n-1;i>0;i--){
        l=k=0;
        for (int j=i+1;j<=n;j++){
            if (b[j][1]>=b[i][1]&&b[j][2]>l){
                l=b[j][2];
                k=j;
            }
        }
        if (l>0){
            b[i][2]=l+1;
            b[i][3]=k;
        }
    }
    k=1;
    for (int j=1;j<=n;j++)
    if (b[j][2]>b[k][2]) k=j;
    cout<<b[k][2];
    return 0;
}

100分

by furina_1013 @ 2024-10-07 09:58:52

DP太麻烦了

#include<bits/stdc++.h>
using namespace std;
int dp[10001],n,a[10001],maxn=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1]=1;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++) if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
        maxn=max(dp[i],maxn);
    }
    cout<<maxn;
    return 0;
}

by luyulin521 @ 2024-10-07 10:02:37

<!DOCTYPE html> <html class="no-js" lang="zh"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no"> <meta name="csrf-token" content="1728352863:H66m0mA0xDB4ToMEXkGG6+xlBYmpDMPpFCvzIETirkQ="> <meta name="renderer" content="webkit"> <meta http-equiv="Content-Security-Policy" content="default-src 'unsafe-inline' luogu.com .luogu.com luogu.com.cn .luogu.com.cn luogu.org .luogu.org .cnzz.com luoguprivate.oss-cn-hangzhou.aliyuncs.com luogu.oss-cn-hangzhou.aliyuncs.com wss: blob:; img-src data:; font-src data:; worker-src data: blob:; frame-src https://player.bilibili.com https://www.bilibili.com"> <title>讨论 100分(第一个点不过）求调 - Luogu Spilopelia</title> <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" media="screen"/> <link rel="stylesheet" href="https://fecdn.luogu.com.cn/luogu/loader.css?ver=20240818"> <script>window._feInjection = JSON.parse(decodeURIComponent("%7B%22code%22%3A200%2C%22currentTemplate%22%3A%22DiscussShow%22%2C%22currentData%22%3A%7B%22forum%22%3A%7B%22name%22%3A%22B3637%20%5Cu6700%5Cu957f%5Cu4e0a%5Cu5347%5Cu5b50%5Cu5e8f%5Cu5217%22%2C%22type%22%3A2%2C%22slug%22%3A%22B3637%22%2C%22color%22%3A%22orange-3%22%2C%22problem%22%3A%7B%22pid%22%3A%22B3637%22%2C%22type%22%3A%22B%22%2C%22title%22%3A%22%5Cu6700%5Cu957f%5Cu4e0a%5Cu5347%5Cu5b50%5Cu5e8f%5Cu5217%22%2C%22difficulty%22%3A3%2C%22submitted%22%3Afalse%2C%22accepted%22%3Afalse%7D%7D%2C%22post%22%3A%7B%22id%22%3A952551%2C%22title%22%3A%22100%5Cu5206%28%5Cu7b2c%5Cu4e00%5Cu4e2a%5Cu70b9%5Cu4e0d%5Cu8fc7%5Cuff09%5Cu6c42%5Cu8c03%22%2C%22author%22%3A%7B%22uid%22%3A1292673%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F1292673.png%22%2C%22name%22%3A%22A_yixiubro%22%2C%22slogan%22%3A%22%23%5Cu300a%5Cu300a%5Cu9cb2%5Cu300b%5Cu300b%5Cu5317%5Cu51a5%5Cu6709%5Cu9c7c%5Cuff0c%5Cu5176%5Cu540d%5Cu4e3a%5Cu9cb2%5Cu3002%5Cu9cb2%5Cu4e4b%5Cu5927%5Cuff0clonglong%5Cu88c5%5Cu4e0d%5Cu4e0b%5Cu3002%5Cu5316%5Cu800c%5Cu4e3a%5Cu9e1f%5Cuff0c%5Cu5176%5Cu540d%5Cu4e3a%5Cu9e4f%5Cuff0c%5Cu9e4f%5Cu4e4b%5Cu5927%5Cuff0c10%5Cu4e2a%5Cu9ad8%5Cu7cbe%5Cu5ea6%5Cu88c5%5Cu4e0d%5Cu4e0b%5Cuff0c%5Cu538b%5Cu5165C%5Cu76d8%5Cu4f1a%5Cu7206%5Cu70b8%5Cu3002%5Cu543e%5Cu4e43%5Cu9cb2%5Cu4e4b%5Cu521b%5Cu9020%5Cu8005%22%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Green%22%2C%22ccfLevel%22%3A0%2C%22background%22%3A%22%22%7D%2C%22time%22%3A1728265611%2C%22forum%22%3A%7B%22name%22%3A%22B3637%20%5Cu6700%5Cu957f%5Cu4e0a%5Cu5347%5Cu5b50%5Cu5e8f%5Cu5217%22%2C%22type%22%3A2%2C%22slug%22%3A%22B3637%22%2C%22color%22%3A%22orange-3%22%7D%2C%22topped%22%3Afalse%2C%22valid%22%3Atrue%2C%22locked%22%3Afalse%2C%22replyCount%22%3A1%2C%22recentReply%22%3A%7B%22id%22%3A6756769%2C%22author%22%3A%7B%22uid%22%3A794188%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F794188.png%22%2C%22name%22%3A%22furina_1013%22%2C%22slogan%22%3A%22%22%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Orange%22%2C%22ccfLevel%22%3A4%2C%22background%22%3A%22%22%7D%2C%22time%22%3A1728266332%7D%2C%22content%22%3A%22%60%60%60cpp%5Cn%23include%20%3Ciostream%3E%5Cnusing%20namespace%20std%3B%5Cnint%20main%28%29%7B%5Cn%5Ctint%20n%2Cl%2Ck%3B%5Cn%5Ctint%20b%5B5001%5D%5B11%5D%3B%5Cn%5Ctcin%3E%3En%3B%5Cn%5Ctfor%20%28int%20i%3D1%3Bi%3C%3Dn%3Bi%2B%2B%29%7B%5Cn%5Ct%5Ctcin%3E%3Eb%5Bi%5D%5B1%5D%3B%5Cn%5Ct%5Ctb%5Bi%5D%5B2%5D%3D1%3B%5Cn%5Ct%5Ctb%5Bi%5D%5B3%5D%3D0%3B%5Cn%5Ct%7D%5Cn%5Ctfor%20%28int%20i%3Dn-1%3Bi%3E0%3Bi--%29%7B%5Cn%5Ct%5Ctl%3Dk%3D0%3B%5Cn%5Ct%5Ctfor%20%28int%20j%3Di%2B1%3Bj%3C%3Dn%3Bj%2B%2B%29%7B%5Cn%5Ct%5Ct%5Ctif%20%28b%5Bj%5D%5B1%5D%3E%3Db%5Bi%5D%5B1%5D%26%26b%5Bj%5D%5B2%5D%3El%29%7B%5Cn%5Ct%5Ct%5Ct%5Ctl%3Db%5Bj%5D%5B2%5D%3B%5Cn%5Ct%5Ct%5Ct%5Ctk%3Dj%3B%5Cn%5Ct%5Ct%5Ct%7D%5Cn%5Ct%5Ct%7D%5Cn%5Ct%5Ctif%20%28l%3E0%29%7B%5Cn%5Ct%5Ct%5Ctb%5Bi%5D%5B2%5D%3Dl%2B1%3B%5Cn%5Ct%5Ct%5Ctb%5Bi%5D%5B3%5D%3Dk%3B%5Cn%5Ct%5Ct%7D%5Cn%5Ct%7D%5Cn%5Ctk%3D1%3B%5Cn%5Ctfor%20%28int%20j%3D1%3Bj%3C%3Dn%3Bj%2B%2B%29%5Cn%5Ctif%20%28b%5Bj%5D%5B2%5D%3Eb%5Bk%5D%5B2%5D%29%20k%3Dj%3B%5Cn%5Ctcout%3C%3Cb%5Bk%5D%5B2%5D%3B%5Cn%5Ctreturn%200%3B%5Cn%7D%5Cn%60%60%60%5Cn%5Cn%5Cn%5B100%5Cu5206%5D%28https%3A%5C%2F%5C%2Fwww.luogu.com.cn%5C%2Frecord%5C%2F180612406%29%22%7D%2C%22replies%22%3A%7B%22perPage%22%3A10%2C%22count%22%3A1%2C%22result%22%3A%5B%7B%22id%22%3A6756769%2C%22author%22%3A%7B%22uid%22%3A794188%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F794188.png%22%2C%22name%22%3A%22furina_1013%22%2C%22slogan%22%3A%22%22%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Orange%22%2C%22ccfLevel%22%3A4%2C%22background%22%3A%22%22%7D%2C%22time%22%3A1728266332%2C%22content%22%3A%22DP%5Cu592a%5Cu9ebb%5Cu70e6%5Cu4e86%5Cn%60%60%60cpp%5Cn%23include%3Cbits%5C%2Fstdc%2B%2B.h%3E%5Cnusing%20namespace%20std%3B%5Cnint%20dp%5B10001%5D%2Cn%2Ca%5B10001%5D%2Cmaxn%3D0%3B%5Cnint%20main%28%29%7B%5Cn%5Ctcin%3E%3En%3B%5Cn%5Ctfor%28int%20i%3D1%3Bi%3C%3Dn%3Bi%2B%2B%29%20cin%3E%3Ea%5Bi%5D%3B%5Cn%5Ctdp%5B1%5D%3D1%3B%5Cn%5Ctfor%28int%20i%3D1%3Bi%3C%3Dn%3Bi%2B%2B%29%7B%5Cn%5Ct%5Ctdp%5Bi%5D%3D1%3B%5Cn%5Ct%5Ctfor%28int%20j%3D1%3Bj%3Ci%3Bj%2B%2B%29%20if%28a%5Bj%5D%3Ca%5Bi%5D%29%20dp%5Bi%5D%3Dmax%28dp%5Bj%5D%2B1%2Cdp%5Bi%5D%29%3B%5Cn%5Ct%5Ctmaxn%3Dmax%28dp%5Bi%5D%2Cmaxn%29%3B%5Cn%5Ct%7D%5Cn%5Ctcout%3C%3Cmaxn%3B%5Cn%5Ctreturn%200%3B%5Cn%7D%5Cn%60%60%60%22%7D%5D%7D%2C%22canReply%22%3Atrue%7D%2C%22currentTitle%22%3A%22%5Cu8ba8%5Cu8bba%20100%5Cu5206%28%5Cu7b2c%5Cu4e00%5Cu4e2a%5Cu70b9%5Cu4e0d%5Cu8fc7%5Cuff09%5Cu6c42%5Cu8c03%22%2C%22currentTheme%22%3A%7B%22id%22%3A1%2C%22header%22%3A%7B%22type%22%3A2%2C%22color%22%3A%5B%5B35%2C37%2C38%2C1%5D%2C%5B65%2C67%2C69%2C1%5D%5D%2C%22degree%22%3A90%2C%22blur%22%3A0%2C%22brightness%22%3A0%2C%22position%22%3A%5B50%2C50%5D%2C%22repeat%22%3A0%2C%22CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CHeaderFooterConfig%22%7D%2C%22sideNav%22%3A%7B%22logoBackgroundColor%22%3A%5B52%2C152%2C219%2C1%5D%2C%22color%22%3A%5B52%2C73%2C94%2C1%5D%2C%22invertColor%22%3Afalse%2C%22__CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CSideNavConfig%22%7D%2C%22footer%22%3A%7B%22type%22%3A2%2C%22color%22%3A%5B%5B51%2C51%2C51%2C1%5D%5D%2C%22degree%22%3A0%2C%22blur%22%3A0%2C%22brightness%22%3A0%2C%22CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CHeaderFooterConfig%22%7D%7D%2C%22currentUser%22%3A%7B%22uid%22%3A1404881%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F1404881.png%22%2C%22name%22%3A%22luyulin521%22%2C%22slogan%22%3A%22%5Cu6211%5Cu89c2%5Cu4f17%5Cu751f%5Cu7686%5Cu8349%5Cu6728%5Cuff0c%5Cu552f%5Cu6709%5Cu89c1%5Cu4f60%5Cu662f%5Cu9752%5Cu5c71%5Cu3002%22%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Blue%22%2C%22ccfLevel%22%3A0%2C%22background%22%3A%22%22%2C%22verified%22%3Atrue%2C%22followingCount%22%3A0%2C%22followerCount%22%3A0%2C%22ranking%22%3Anull%2C%22unreadMessageCount%22%3A0%2C%22unreadNoticeCount%22%3A0%7D%2C%22currentTime%22%3A1728266463%7D"));window._feConfigVersion=1726211203;window._tagVersion=1728261612;</script> <script src="https://fecdn.luogu.com.cn/luogu/loader.js?ver=20240818" charset="utf-8" defer></script> </head> <body> <div id="app"> <h1>100分(第一个点不过）求调</h1> <h2><a href="/discuss?forum=B3637">B3637 最长上升子序列</a></h2>

        <p>
        DP太麻烦了

#include&lt;bits/stdc++.h&gt;
using namespace std;
int dp[10001],n,a[10001],maxn=0;
int main(){
    cin&gt;&gt;n;
    for(int i=1;i&lt;=n;i++) cin&gt;&gt;a[i];
    dp[1]=1;
    for(int i=1;i&lt;=n;i++){
        dp[i]=1;
        for(int j=1;j&lt;i;j++) if(a[j]&lt;a[i]) dp[i]=max(dp[j]+1,dp[i]);
        maxn=max(dp[i],maxn);
    }
    cout&lt;&lt;maxn;
    return 0;
}

        <br />
        <small><i>by furina_1013 @ 2024-10-07 09:58:52</i></small>
    </p>
    <hr>

        |

    <noscript>
        <h3>请<b style="color:#f00;">不要禁用</b>脚本，否则网页无法正常加载</h3>
    </noscript>

by A_yixiubro @ 2024-10-11 21:07:34

@furina_1013 谢谢大佬，已关

by A_yixiubro @ 2024-10-11 21:08:17

谢谢，此贴结。