这个……真心看不出来是个DP,我在树状数组的康庄大道上欢快的奔跑了一下午……看了题解才发现错的有多离谱。
参考:http://www.cnblogs.com/kuangbin/archive/2012/11/11/2765329.html
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define LL long long int using namespace std; const int MAXN = 1000100; int val[MAXN]; int pos[MAXN]; int cnt[MAXN]; int diff[MAXN]; bool vis[MAXN]; LL dp[MAXN]; int N; int main() { while ( scanf( "%d", &N ) == 1 && N ) { memset( cnt, 0, sizeof(int)*(N+4) ); memset( pos, 0, sizeof(int)*(N+4) ); for ( int i = 1; i <= N; ++i ) { scanf( "%d", &val[i] ); ++cnt[ i - pos[ val[i] ] ]; pos[ val[i] ] = i; } memset( vis, false, sizeof(bool)*(N+4) ); diff[1] = 1; vis[ val[N] ] = true; for ( int i = 2; i <= N; ++i ) { if ( vis[ val[N-i+1] ] ) diff[i] = diff[i - 1]; else { diff[i] = diff[i - 1] + 1; vis[ val[N-i+1] ] = true; } } int tot = N; dp[1] = N; for ( int i = 2; i <= N; ++i ) { dp[i] = dp[i - 1] - diff[i - 1]; tot -= cnt[i - 1]; dp[i] += tot; } int Q; scanf("%d", &Q ); while ( Q-- ) { int w; scanf("%d", &w); printf("%I64d ", dp[w] ); } } return 0; }