2010-1144

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意是HH要bg他的n个朋友，第i个朋必须友要在di天前bg，每天最多只能bg一个朋友。[[BR]]
动态规划，设f[j][k]表示前k天bg前j个朋友，显然第i个朋友最早可以bg的时间是第i天。动态转移方程 f[j][k]= sigma( f[j-1][i] )(j-1 <= i <= k-1), 初始值f[0][0]=1。[[BR]]
可以使用滚动数组优化，但每次要memset为0。[[BR]]
可以使用两个小优化，一个是缩小di的范围，一个是判断是否有解。

{{{
#!cpp
#include<cstdio>
#include<cstring>
long f[2][20001];
int main()
{
        long n,j,k,i,t,a[501];
        while(scanf("%ld",&n)!=EOF)
        {
                for (j=1;j<=n;++j) scanf("%ld",&a[j]);
                for (j=n;j>1;--j) if (a[j]-1<a[j-1]) a[j-1]=a[j]-1;//优化范围 
                  if (a[1]<=0) { printf("0\n"); continue; } //判断是否存在可行解没有则直接输出 
                  memset(f,0,sizeof(f));f[0][0]=1;
                for (j=1;j<=n;++j)
                {
                        memset(f[j&1],0,sizeof(f[j&1]));                        
                        i=f[(j-1)&1][j-1]%100000009;
                        for (k=j;k<=a[j];++k) 
                        {
                                f[j&1][k]=i;
                                i=(i+f[(j-1)&1][k])%100000009;
                        }
                }
                i=0;
                for (j=n;j<=a[n];++j) i= (i+f[n&1][j])%100000009;

                printf("%ld\n",i);
        }
        return 0;
}
}}}

题目大意是HH要bg他的n个朋友，第i个朋必须友要在di天前bg，每天最多只能bg一个朋友。

动态规划，设f[j][k]表示前k天bg前j个朋友，显然第i个朋友最早可以bg的时间是第i天。动态转移方程 f[j][k]= sigma( f[j-1][i] )(j-1 <= i <= k-1), 初始值f[0][0]=1。

可以使用滚动数组优化，但每次要memset为0。

可以使用两个小优化，一个是缩小di的范围，一个是判断是否有解。

#include<cstdio>
#include<cstring>
long f[2][20001];
int main()
{
        long n,j,k,i,t,a[501];
        while(scanf("%ld",&n)!=EOF)
        {
                for (j=1;j<=n;++j) scanf("%ld",&a[j]);
                for (j=n;j>1;--j) if (a[j]-1<a[j-1]) a[j-1]=a[j]-1;//优化范围 
                  if (a[1]<=0) { printf("0\n"); continue; } //判断是否存在可行解没有则直接输出 
                  memset(f,0,sizeof(f));f[0][0]=1;
                for (j=1;j<=n;++j)
                {
                        memset(f[j&1],0,sizeof(f[j&1]));                        
                        i=f[(j-1)&1][j-1]%100000009;
                        for (k=j;k<=a[j];++k) 
                        {
                                f[j&1][k]=i;
                                i=(i+f[(j-1)&1][k])%100000009;
                        }
                }
                i=0;
                for (j=n;j<=a[n];++j) i= (i+f[n&1][j])%100000009;
                printf("%ld\n",i);
        }
        return 0;
}