2016年2月15日 星期一

[Codeforces 626F]Group Projects

由於順序不重要,我們乾脆先把這些學生排序好

可以發現,對於每一組,我們只需要關心最大值和最小值

因此,我們可以構造一個$DP$,$DP[g][i]$代表目前有效$imbalance$是$i$,有$g$組還沒完成 (還沒有上界)
當一個學生$s$加進來時,有以下四種情況 (假設從$DP[g][i]$轉移)
轉移後的有效$imbalance$一定是$g*(s-s_{上一個})$,令它為$i_{0}$
1. 加進$g$組中的其中一組,以權重$g$轉移到$DP[g][i_{0}]$
2. 自成新的一組,在新的一組中以$s$當作下界,轉移到$DP[g+1][i_{0}]$
3. 從$g$組中選一組,以$s$當作上界,這組就完成了,以權重$g$轉移到$DP[g-1][i_{0}]$
4. 自成新的一組,且這組只有$s$一個人,轉移到$DP[g][i_{0}]$

可以使用$N*N*K$的三維陣列一層一層轉移,或較省空間的滾動陣列
最終答案即是$\sum_{i=0}^{K} DP[0][i]$

時間複雜度:$O(N^{2}K)$

code:
#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
int N,K,S[201];
LL DP[2][201][1001];
void Add(LL &a,const LL &b){(a+=b)%=MOD;}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
        for(int i=1;i<=N;i++)scanf("%d",&S[i]);
        sort(S+1,S+N+1),S[0]=0;
        for(int d=0;d<2;d++)for(int i=0;i<=N;i++)for(int j=0;j<=K;j++)DP[d][i][j]=0LL;
        DP[0][0][0]=1LL;
        int d=0;
        for(int idx=1;idx<=N;idx++,d^=1)
        {
            for(int g=0;g<=N;g++)for(int i=0;i<=K;i++)DP[d^1][g][i]=0LL;
            for(int g=0;g<=N;g++)for(int i=0;i<=K;i++)if(DP[d][g][i])
            {
                const int nxti=i+g*(S[idx]-S[idx-1]);
                if(nxti>K)break;
                Add(DP[d^1][g][nxti],g*DP[d][g][i]);//Add to existing group
                Add(DP[d^1][g+1][nxti],DP[d][g][i]);//Create new group
                if(g>0)Add(DP[d^1][g-1][nxti],g*DP[d][g][i]);//Add to and close one group
                Add(DP[d^1][g][nxti],DP[d][g][i]);//Create and close new group
            }
        }
        LL ans=0LL;
        for(int i=0;i<=K;i++)Add(ans,DP[d][0][i]);
        printf("%I64d\n",ans);
    }
    return 0;
}

沒有留言:

張貼留言

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