社区讨论

请问为什么我枚举i ,j作为区间两端点来递推会出问题

P4290[HAOI2008] 玩具取名参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@m5xk8e8v
此快照首次捕获于
2025/01/15 15:08
去年
此快照最后确认于
2025/01/15 15:11
去年
查看原帖
我的思路是枚举ij为前后端点的区间,然后该区间是由[i,k]和[k+1][j]更新得到。 请问这题一定要严格按照先把所有小区间推完再推大区间的思路做吗,如果按我推的顺序是会有遗漏吗? 求各位大佬解答…
程序如下
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 205
  using namespace std;
char ch1[5][N] , ch2[5][N];
char s[N];
int dp[N][N][5];
int num[N];
int change_num(char ch){
    if(ch == 'W') return 1;
    if(ch == 'I') return 2;
    if(ch == 'N') return 3;
    if(ch == 'G') return 4;
}
char change_ch(int x){
    if(x == 1) return 'W';
    if(x == 2) return 'I';
    if(x == 3) return 'N';
    if(x == 4) return 'G';
}
int main()
{
    for(int i = 1 ; i <= 4 ; i++) cin >> num[i];
    for(int i = 1 ; i <= 4 ; i++)
        for(int j = 1 ; j <= num[i] ; j++) cin >> ch1[i][j] >> ch2[i][j];
    scanf("%s" , s + 1);
    int n = strlen(s + 1);
    for(int i = n - 1 ; i >= 1 ; i -= 2)
        for(int j = i + 1 ; j <= n ; j += 2)
        {
            if(j == i + 1){
                for(int k = 1 ; k <= 4 ; k++)
                    for(int w = 1 ; w <= num[k] ; w++)
                        if(s[i] == ch1[k][w] && s[j] == ch2[k][w]) dp[i][j][k] = 1;
                continue;
            }
            for(int k = i + 1 ; k <= n - 2 ; k += 2){
                for(int p = 1 ; p <= 4 ; p ++)
                    for(int w = 1 ; w <= num[p] ; w++){
                        if(dp[i][k][change_num(ch1[p][w])] && dp[k + 1][j][change_num(ch2[p][w])]) dp[i][j][p] = 1;
                    }
            }
        }
    bool f = 0;
    for(int i = 1 ; i <= 4 ; i++)
        if(dp[1][n][i]){
            cout << change_ch(i);
            f = 1;
        }
    if(!f) cout << "The name is wrong!";
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...