golemon. 2022-02-08 14:21 采纳率: 40%
浏览 13
已结题

动态规划 lcs 打印序列

问题遇到的现象和发生背景

https://atcoder.jp/contests/dp/tasks/dp_f

问题相关代码,请勿粘贴截图
#include<bits/stdc++.h>
using namespace std;
const int M = 5000;
std::string ssz[M][M];
std::string a;
std::string b;
int dp[M][M];
int main()
{

    getline(cin,a);
    getline(cin,b);
    string j = " ";
    a=j+a;
    b=j+b;
    for(int i = 1;i <= a.size(); i++)
        for(int j = 1; j <= b.size(); j++){
            if(a[i] == b[j]) {dp[i][j]=dp[i-1][j-1]+1;ssz[i][j]=b[j];}
            else {
                if(dp[i-1][j]>dp[i][j-1]) {
                    dp[i][j]=dp[i-1][j];
                    ssz[i][j]=ssz[i-1][j];
                }
                else {
                    dp[i][j]=dp[i][j-1];
                    ssz[i][j]=ssz[i][j-1];
                }
            }
        }
        stack<string>s;
        int n,m;
        n=a.size(); m=b.size();
        while(dp[n][m]) {
            
            if(dp[n-1][m-1] +1 ==dp[n][m]) {s.push(ssz[n][m]);
                n--;m--;
            }
            else {
                if(dp[n-1][m]>=dp[n][m-1]) {
                        n--;
                }
                else {
                        m--;
            }
        }
        }
        while(!s.empty()){
            cout<<s.top();
            s.pop();
        }
}

运行结果及报错内容 样例对,但是递交不对
我的解答思路和尝试过的方法
我想要达到的结果
  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 2月16日
    • 创建了问题 2月8日

    悬赏问题

    • ¥20 verilog状态机方法流水灯
    • ¥15 pandas代码实现不了意图
    • ¥15 GD32H7 从存储器到外设SPI传输数据无法重复启用DMA
    • ¥25 LT码在高斯信道下的误码率仿真
    • ¥45 渲染完成之后将物体的材质贴图改变,自动化进行这个操作
    • ¥15 yolov5目标检测并显示目标出现的时间或视频帧
    • ¥15 电视版的优酷可以设置电影连续播放吗?
    • ¥50 复现论文;matlab代码编写
    • ¥30 echarts 3d地图怎么实现一进来页面散点数据和卡片一起轮播
    • ¥15 数字图像的降噪滤波增强