I题
思路:动态规划,f[i]表示选择使用第i个壁纸最终使用至少两种壁纸的方案数
计算方法:f[i]等于使用了天后,
(1)又使用了至少两张壁纸,枚举天后的其第一张壁纸即
(2)又只使用了一张壁纸,即种;
得到
为了减少计算量,用sums[i]保存sum(f[i],···,f[n])
AC代码:
#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 #define MAX 1000001 typedef long long int ll; int n; int dat[MAX]; int f[MAX]; int sums[MAX]; void solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> dat[i]; if (dat[i] == 0) dat[i] = 1; } for (int i = n; i > 0; i--) { if (i + dat[i] <= n) { f[i] = (sums[i + dat[i]] + (n - (i + dat[i]) + 1)) % MOD; } sums[i] = (sums[i + 1] + f[i]) % MOD; } cout << sums[1] << endl; } int main() { int n__ = 1; // cin >> n__; while (n__--) { solve(); } return 0; }