C++代码本地运行正常 USACO评测输出异常 多IO方式均失效求助

问题排查结果 #

你代码的核心问题有三个，均为低级失误：

• 1. dp数组未初始化，默认是内存中的随机垃圾值
     你本地运行时刚好栈内存初始值都是0所以结果正确，评测系统的栈内存是脏数据，所以结果随机异常，你输出的奇怪数字本质就是随机垃圾值计算后的结果。
• 2. 状态转移的边界判断完全错误
     你写的if(n)永远为真（输入的n最少为1），当s=0时你直接访问s-1也就是下标为-1的dp元素，属于数组越界，读取的是非法内存的值；同时i=1时访问i-1=0的dp状态，你也没有初始化dp[0]层的初始值。
• 3. 变长数组(VLA)不是标准C++语法，USACO的评测编译器对VLA的支持存在兼容隐患，最好换成静态数组或者vector实现。

修正后的代码 #

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    char s[10];
    int gestures[105] = {0};
    // 这里假设n和k的上限是1e2，如果题目上限更高改大数组即可，或者用vector
    int dp[105][105][3] = {0}; 
    for (int i = 1; i <= n; i++){
        scanf("%s", s);
        if (s[0]=='H') gestures[i] = 0;
        else if (s[0]=='P') gestures[i] = 1;
        else gestures[i] = 2;
    }
    int res = 0;
    for (int i = 1; i <= n; i++){
        for (int s = 0; s <= k; s++){
            for (int p1 = 0; p1 < 3; p1++){
                // 先继承不切换手势的状态
                dp[i][s][p1] = dp[i-1][s][p1];
                // 只有切换次数>=1的时候才考虑切换手势的情况
                if(s >= 1){
                    dp[i][s][p1] = max(dp[i][s][p1], dp[i-1][s-1][(p1+1)%3]);
                    dp[i][s][p1] = max(dp[i][s][p1], dp[i-1][s-1][(p1+2)%3]);
                }
                // 加上当前轮的得分
                dp[i][s][p1] += (p1 == gestures[i]);
                if (i == n) res = max(res, dp[i][s][p1]);
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

如果题目n和k的上限更高，把数组改到对应大小即可，或者用vector动态分配：

vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(3, 0)));

内容的提问来源于stack exchange，提问作者ministMinion