2016年1月25日 星期一

[UVa 12906]Maximum Score

For simplicity, we call the sequence that fit the restriction of $x_{i}$ $S_{i}$.
We can know that the length of $S_{i}$ would not exceed number of $x_{j}$, such that $x_{j}\leq x_{i}$
If we sort the numbers in increasing order, all $S_{i}$ would reach the maximum length!
So we can calculate the first answer according to descriptions above.

For the second answer, we know that for each $S_{i}$, all values $<x_{i}$ on the left of $x_{i}$ must form a non-increasing sequence, all values$<x_{i}$ on the right of $x_{i}$ must form a non-decreasing sequence, or $S_{i}$ would not be able to reach the maximum length.
So the optimal permutations are composed of a non-increasing sequence and a non-decreasing sequence.

Let's sort the pairs: $\{(v_{k},f_{k})\}$
The number of such optimal permutations is $\prod_{i=1}^{P-1}  (f_{i}+1)$

If you don't know why, let's call the location of maximum values $peak$.
for every $v_{k}$, we have $f_{k}$ of such numbers, we can decide to put $0,1,2,...,f_{k}$ on the left of $peak$ and $f_{k},f_{k}-1,f_{k}-2,...,0$ on the right of $peak$, so there are $f_{k}+1$ ways to assign values of $v_{k}$. Therefore, you know, the number of ways to assign all $v_{k}$ is $\prod_{i=1}^{P-1}  (f_{i}+1)$. :)

Total time complexity: $O(P\log P)$

Note:
1. The first answer is no need to modulo $10^{9}+7$.
2. The first answer must be handled with unsigned long long, not long long.

code:
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
const LL MOD=1000000007LL;
//LL LEVEL[100001];
int N;
vector<pair<int,LL> >S;
LL Solve1()
{
    LL ans=0LL,sum=0LL;
    for(const auto &p:S)
    {
        sum+=p.second;//)%=MOD;
        ans+=sum*p.second;//)%=MOD;
    }
    return ans;
}
int main()
{
//    LEVEL[0]=1LL;
//    for(int i=1;i<=100000;i++)LEVEL[i]=(LEVEL[i-1]*i)%MOD;
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d",&N);
        S.clear();
        for(int i=0,v,f;i<N;i++)scanf("%d%d",&v,&f),S.push_back(make_pair(v,(LL)f));
        sort(S.begin(),S.end());
        const LL ans1=Solve1();
        LL ans2=1LL;
//        for(const auto &p:S)(ans2*=LEVEL[p.second])%=MOD;
        S.pop_back();
        for(const auto &p:S)(ans2*=p.second+1LL)%=MOD;
        static int kase=1;
        printf("Case %d: %llu %llu\n",kase++,ans1,ans2);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原

注意:只有此網誌的成員可以留言。