为什么会WA

原题链接：7967.星球游玩

AAA碳水回收哥

2025-12-13 21:50:08

发布于：浙江

23阅读

0回复

0点赞

代码和思路：

#include<iostream>
using namespace std;

string a[10010];
int n;

struct pep{//定义结构体，用来存储该方案的人数和对应的人
    int s=0;
    string name="";
}dp[10010];

pep d(int k){//dp函数，用于求解前K个游客的最优解
    if(dp[k].s){//如果已经求解过，那么直接返回结果
        return dp[k];
     }
    if(k==n-1){//特殊情况
        return {1,a[n-1]};
    }
    pep mx={0,""};
    pep l;
    for(int i = 0;i<k;i++){//求解前K个游客的最优解
        if(a[k]>a[i]){//如果符合上升子序列的要求
            l=d(i);//求出它的长度
            if(l.s>mx.s){//比记录还长，更新记录
                mx=l;
            }
        }
    }
    dp[k]={mx.s+1,mx.name+a[k]};//跟新dp数组
    return dp[k];
}

int main(){
    string s,cns="";
    int cnt=0;
    cin >> s;
    cns=s[0];
    for(int i = 1;i<s.size();i++){
        if(s[i]<'a'){//如果是名字开头
            a[cnt++]=cns;//跟新名字数量，将名字存入存储数组
            cns=s[i];//跟新纪录变量
        }else{
            cns+=s[i];//跟新纪录变量
        }
    }
    a[cnt++]=cns;//处理末尾
    int n=cnt;
    pep l,mx={0,""};
    for(int i = 0;i<n;){
        l=d(i++);  //持续查找当前最优解
        if(l.s>mx.s){
            mx=l;//持续维护当前最优解
        }
        else if(l.name[l.name.size()-1]<mx.name[mx.name.size()-1] && l.s==mx.s){
            mx=l;//持续维护当前最优解
        }
    }
    cout << mx.name;
}

时间复杂度O(N^2)

有帮助，赞一个

去预览

0/2000

全部评论 1

茅翰清
I don't know

2025-12-14 来自浙江
0

全部评论 1

热门讨论