SRM501 Div1 Medium(500), Div2 Hard(1000) FoxAverageSequence

TopCoder

FoxAverageSequence

動的計画法。数列の合計・直前のA[i]の値・A[i-1]≦A[i]が成り立つか、のそれぞれに対してbeautifulな数列の個数を覚えておく。A[i-1]の値は必要ない。

#include <vector>
using namespace std;

class FoxAverageSequence{public:
int theCount( vector <int> seq )
{
    int M = 1000000007;
    int n = (int)seq.size();

    static int T[40][1601][41][2];
    //  [p][s][a][f]
    //      sum[0≦i≦p]A[i] = s
    //      A[i] = a
    //      f==0ならばA[p-1]＞A[p]　f==1ならばA[p-1]≦A[p]
    //      なる数列の個数
    memset(T,0,sizeof T);

    for ( int a=0; a<=40; a++ )
    if ( seq[0]==-1 || seq[0]==a )
        T[0][a][a][1]++;

    for ( int p=1; p<n; p++ )
        for ( int s=0; s<=40*p; s++ )
            for ( int a0=0; a0<=40; a0++ )
            if ( seq[p]==-1 || seq[p]==a0 )
            if ( a0*p<=s )
                for ( int a1=0; a1<=40; a1++ )
                {
                    if ( a1<=a0 )
                        T[p][s+a0][a0][a1<=a0] += T[p-1][s][a1][0],
                        T[p][s+a0][a0][a1<=a0] %= M;
                    T[p][s+a0][a0][a1<=a0] += T[p-1][s][a1][1];
                    T[p][s+a0][a0][a1<=a0] %= M;
                }

    int ans = 0;
    for ( int s=0; s<=40*n; s++ )
    for ( int a=0; a<=40; a++ )
    for ( int f=0; f<=1; f++ )
        ans += T[n-1][s][a][f],
        ans %= M;

    return ans;
}};