首页 > 试题广场 > 还原
[编程题]还原
  • 热度指数:907 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有一个含有n个数字的序列,每个数字的大小是不超过200的正整数,同时这个序列满足以下条件: 
1. a_1<=a_2
2. a_n<=a_(n-1) (此时n>2)
3. a_i<=max(a_{i-1},a_{i+1}) 

但是很不幸的是,在序列保存的过程中,有些数字丢失了,请你根据上述条件,计算可能有多少种不同的序列可以满足以上条件。


输入描述:
输入第一行是一个n,表示这个序列的长度。(3<=n<=10^4)

输入第二行有n个非负整数,中间用空格隔开,如果数字为0,说明这个数字丢失了,其他数字则都在1-200之间。


输出描述:
输出仅包含一个整数,即方案数对998244353取模的结果。
示例1

输入

3
2 0 1

输出

1
这个题目我都看不懂  是我太菜了吗  index 到底是从0开始 还是从1还是
编辑于 2019-07-28 03:53:15 回复(7)
//回溯法  想想都应该是超时的  错误提示时间复杂度过大
#include<iostream>
(720)#include<vector>
#include<algorithm>

using namespace std;

const long long ModNum = 998244353;
long long ans = 0;
void BackTrack(vector<int> &v, vector<int> temp, int i) {
	int maxNum;
	if (i == v.size()) {
		ans++;
		ans %= 998244353;
		return;
	}
	if (v[i] != 0) {
	
		if (i == 0) {
			temp.push_back(v[i]);
			BackTrack(v, temp, i + 1);
			temp.pop_back();
		}
		else if (i == 1) {
			if (v[i] >= temp.back()) {
				temp.push_back(v[i]);
				BackTrack(v, temp, i + 1);
				temp.pop_back();
			}
		}
		else {
			maxNum = max(temp[temp.size() - 2], v[i]);
			if (temp[temp.size() - 1] <= maxNum && i != v.size() - 1) {
				temp.push_back(v[i]);
				BackTrack(v, temp, i + 1);
				temp.pop_back();
			}
			else if (temp[temp.size() - 1] <= maxNum && i == v.size() - 1 && v[i] <= temp.back()){
				temp.push_back(v[i]);
				BackTrack(v, temp, i + 1);
				temp.pop_back();
			}	
		}
	}
	else {
		for (int j = 1; j <= 200; j++) {
			if (i == 0) {
				temp.push_back(j);
				BackTrack(v, temp, i + 1);
				temp.pop_back();
			}
			else if (i == 1) {
			
				if (j >= temp.back()) {
					temp.push_back(j);
					BackTrack(v, temp, i + 1);
					temp.pop_back();
				}
			}
			else {
				maxNum = max(temp[temp.size() - 2], j);
				if (temp[temp.size() - 1] <= maxNum && i != v.size()-1) {
					temp.push_back(j);
					BackTrack(v, temp, i + 1);
					temp.pop_back();
				}
				else if (temp[temp.size() - 1] <= maxNum && i == v.size() - 1 && j <= temp.back()) {
					temp.push_back(j);
					BackTrack(v, temp, i + 1);
					temp.pop_back();
				}
			}
		}
	}
	return;
}
int main(void) {
	int n;
	cin >> n;
	vector<int> v;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}
	vector<int> temp;
	BackTrack(v, temp, 0);
	cout << ans << endl;

	return 0;
}

发表于 2020-05-09 18:18:00 回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long mod = 998244353;
        int N = sc.nextInt();
        int[] arr = new int[N + 10];
        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
        long[][][] res = new long[N + 10][210][3];
        long[] s1 = new long[210];
        long[] s2 = new long[210];
        //初始化
        for (int i = (arr[1] == 0 ? 1 : arr[1]); i <= (arr[1] == 0 ? 200 : arr[1]); i++) {
            for (int j = (arr[2] == 0 ? 1 : arr[2]); j <= (arr[2] == 0 ? 200 : arr[2]); j++) {
                if (i == j) res[2][j][1]++;
                else if (i < j) res[2][j][2]++;
            }
        }
        for (int j = 1; j <= 200; j++) {
            s1[j] = s1[j - 1] + res[2][j][0] + res[2][j][1] + res[2][j][2];
            s2[j] = s2[j - 1] + res[2][j][0] + res[2][j][1];
        }
        //更新结构
        for (int i = 3; i <= N; i++) {
            for (int j = (arr[i] == 0 ? 1 : arr[i]); j <= (arr[i] == 0 ? 200 : arr[i]); j++) {
                res[i][j][0] = (s2[200] - s2[j]) % mod;
                res[i][j][1] = (res[i - 1][j][0] + res[i - 1][j][1] + res[i - 1][j][2]) % mod;
                res[i][j][2] = s1[j - 1] % mod;
            }
            for (int j = 1; j <= 200; j++) {
                s1[j] = s1[j - 1] + res[i][j][0] + res[i][j][1] + res[i][j][2];
                s2[j] = s2[j - 1] + res[i][j][0] + res[i][j][1];
            }
        }
        long ans = 0;
        for (int j = (arr[N] == 0 ? 1 : arr[N]); j <= (arr[N] == 0 ? 200 : arr[N]); j++) {
            ans = (ans + res[N][j][0] + res[N][j][1]) % mod;
        }
        System.out.println(ans);
    }
}
https://www.acwing.com/solution/acwing/content/1873/
发表于 2020-04-16 23:23:56 回复(0)
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为20.00%

用例:
6
0 0 2 6 0 0

对应输出应该为:

40200

你的输出为:

0

感觉数据有问题啊   0 0 2 6 0 0   这个就已经不满足要求了    a[3] = 2  a[4] = 6   a[3] < a[4] 题目要求 a[n] <= a[n-1] 也就是 a[4] <= a[3]  方案肯定为0啊这种? 这题太奇怪了
发表于 2020-01-11 13:54:40 回复(1)