题意: 给一个数集和一个数d,问满足下列要求的排列数(相同的数要区分): a[i]+d>=a[i+1] ( i in [1,n) )
因为数的给出顺序不重要,所以先排序,假如我们已经解决了前i个数的答案,考虑前i+1个数,即我们可以将第i+1个数放在哪,然后发现对于前i个数的每一种方案,我们都可以选择将第i+1个数放在大于等于它-d的数的上面,从而形成一种新的方案(当然直接可以放在地上),然后就完了.
收获:
1. 对于不重要的东西(如原序列的顺序),可以直接舍弃
2. 减小问题规模,发现小规模的问题和比它大一数据规模的问题之间的联系.
1 /************************************************************** 2 Problem: 2013 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:988 ms 7 Memory:10492 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 #define N 620010 13 #define Mod 1000000009 14 using namespace std; 15 16 typedef long long dnt; 17 18 int n; 19 dnt h[N], d; 20 dnt dp[N]; 21 22 int main() { 23 scanf( "%d%lld", &n, &d ); 24 for( int i=1; i<=n; i++ ) 25 scanf( "%lld", h+i ); 26 sort( h+1, h+1+n ); 27 dnt cur = 1; 28 for( int i=1; i<=n; i++ ) { 29 int j = lower_bound( h+1, h+i, h[i]-d ) - h; 30 cur = cur*(i-j+1) % Mod; 31 } 32 printf( "%lld\n", cur ); 33 } 34
原文：http://www.cnblogs.com/idy002/p/4578552.html
