社区讨论

求大家帮忙看一下我这里题解哪里格式错了，我不太理解管理员给的原因

CChenZQ
灌水区参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lszv5l50
此快照首次捕获于
2024/02/24 17:13
2 年前
此快照最后确认于
2024/02/24 20:43
2 年前
查看原帖
很遗憾，您上传的题解 数字串 Number String 未能通过审核。原因是 【中文标点符号】与【英文、数字、公式或汉字】之间不应添加多余空格；数学公式中的文本应使用 \text，字符串应使用 \texttt；审核管理员：shinzanmono，对审核结果有疑问请私信交流。 。 题意：给你一个字符串 ss，s[i]=Ds[i] = D 表示排列中 a[i]>a[i+1]a[i] > a[i+1]，s[i]=Is[i] = I 表示排列中 a[i]<a[i+1]a[i] < a[i+1]，s[i]=?s[i] = ? 表示无限制。
dp[i][j]dp[i][j] 表示前 ii 个满足字符串条件的结尾为 jj 的 ii 的排列。
如果 s[i−1]s[i-1] 是 I，那么 dp[i][j]=dp[i−1][1]+dp[i−1][2]+⋯+dp[i−1][j−1]dp[i][j] = dp[i-1][1] + dp[i-1][2] + \dots + dp[i-1][j-1]
如果 s[i−1]s[i - 1] 是 D，那么 dp[i][j]=dp[i−1][j]+dp[i−1][j+1]+⋯+dp[i−1][i]dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + \dots + dp[i-1][i]，因为要令当前位为 jj，如果前面出现过 jj，就令前面的所有大于等于 jj 的数 +1+1，就能构造出新的排列了。比如 1,3,5,2,4{1, 3, 5, 2, 4}，要在第六位插入 33,令 ≥3\ge 3 的数都 +1+1，于是就构造出新的 排列 1,4,6,2,5,3{1, 4, 6, 2, 5, 3}。然后代码的话处理出前缀和 sum[i][j]sum[i][j]，就不用 dp[i][j]dp[i][j] 了。
CPP
#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;
const int maxn = 1e3 + 10;
char s[maxn];
long long dp[maxn][maxn];   //前缀和

int main()
{
    while(scanf("%s", s) != EOF){
        int n = strlen(s);

        dp[0][1] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i + 1; j++){
                dp[i][j] = dp[i][j-1];      //前缀和累加
                if(s[i-1] != 'I') dp[i][j] += dp[i-1][i] - dp[i-1][j-1] + mod;
                if(s[i-1] != 'D') dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= mod;
            }
        }

        printf("%lld\n", dp[n][n+1]);
    }

    return 0;
}

回复

共 6 条回复，欢迎继续交流。

正在加载回复...