4种情况分别为 {321}, {3, 21}, {32, 1}, {3, 2, 1} 数据规模与约定： 其中10%的数据， 1<=n<=10，1<=Ai<=10； 其中20%的数据， 1<=n<=10，1<=Ai<=1000000000000000000（10^18）； 其中30%的数据， 1<=n<=100000，1<=Ai<=10； 其中40%的数据， 1<=n<=100000，1<=Ai<=1000000000000000000（10^18）；
思路：dp[i]表示前i个数，有多少种分割方法。
因此，i+1有这样两种情况：
1.前面没有发生有数重复的情况，则dp[i+1]等于dp数组前面所有的和
（为什么是和呢？）比如 1 2 3 4后面放一个2
他可以是 1 2 【342】 1 2 3【42】 1 2 3 4 【2】
那么把2新加入整个数列得到的新的种数刚好是dp[2]+dp[3]+dp[4]
2.前面发生了有数重复的情况，我们就要找到从这个数开始往前面最靠近这个数的重复的两个数的第一个。
比如：126895968 当我们要加入8时，前面的6和9都有重复的数，如果我们把这个8划分到第一个6后面，显然，有9重复，会影响后面的分割，所以，我们应该划分到第一个9后面。
以上两种情况，处理下就可以。状态转移方程：dp[i] = sum(dp[i-1]...dp[j])【j是前面重复值第一个数的位置】
然后，计算dp[i]的时候,由于我们需要找到前面重复的值，并从那里开始算，如果每次去遍历前面的dp值，会超时，因此用前缀和优化。当然离得最近的重复值位置也需要记录下，也能优化下时间。最后，由于数字最大是18位，而个数最多才100000，因此可以离散化下。
本人java版代码（重复值记录的方法还是有点不好，因为如果没有重复值的时候，其实就是n^2的复杂度，但数据不是很变态的情况可以AC）：
import java.util.*; public class Main{ static Scanner sc = new Scanner(System.in); static int n, cnt = 0, MOD = 1000000007; static int [] dp; static int [] mark; static int [] pre; static int [] num; static Map<Long, Integer> map = new HashMap<Long, Integer>(); public static void main(String[] args) { n = sc.nextInt(); dp = new int[n+1]; dp[0] = 1; mark = new int[n+1]; pre = new int[n+1]; num = new int[n+1]; long tmp; int start; for(int i = 1; i <= n; i++) { tmp = sc.nextLong(); if(!map.containsKey(tmp)) { map.put(tmp, ++cnt); mark[cnt] = i; start = 0; }else { start = mark[map.get(tmp)]; num[i] = start; mark[map.get(tmp)] = i; } for(int j = i-1; j >= start; j--) { if(num[j] > 0) { start = Math.max(start, num[j]); } } dp[i] = (pre[i-1]%MOD - pre[start]%MOD + MOD + dp[start]%MOD)%MOD; pre[i] = (pre[i-1]%MOD + dp[i]%MOD)%MOD; } System.out.println(dp[n]); } }下面是学长的代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define MOD 1000000007 int n; ll a[100005]; map<ll, int> vis; int lst[100005]; ll dp[100005], sum[100005]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } int t = 0; for(int i = 1; i <= n; i++) { if(vis[a[i]] == 0) { vis[a[i]] = i; } else { t = max(t, vis[a[i]]); vis[a[i]] = i; } lst[i] = t - 1; } dp[0] = sum[0] = 1; for(int i = 1; i <= n; i++) { if(lst[i] == -1) { dp[i] = sum[i - 1]; } else { dp[i] = (sum[i - 1] - sum[lst[i]] + MOD) % MOD; } sum[i] = (sum[i - 1] + dp[i]) % MOD; //printf("%d: %lld\n", i, dp[i]); } printf("%lld\n", dp[n]); return 0; }
