hdu 2512（水题，是DP）

前做过这类题的迷你版，n最大值只有25。这道题虽然是2000，但是丝毫不能影响我用样的方法把它切了。

重复一下之前的解释：n张卡分组一共只有n种情况，分别是分一组，两组，三组。。。n组。将i张卡分成j组可以有之前两种情况得来：i-1张卡分成j-1组，只要将第i张卡独立分成一组就行了，或者是i-1张卡分成j组，第i张卡随便插入哪一组都符合条件。

状态转移方程：mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j。

[cpp]
#include<stdio.h>
#include<string.h>
#define N 2005
int mark[N][N];
int main()
{
    int i,j;
    memset(mark,0,sizeof(mark));
    for(i=1;i<=2000;i++)
    {
        mark[i][1]=1;
        mark[i][0]=0;
        for(j=1;j<=2000;j++)
        {
            if(i==j)
            {
                mark[i][j]=1;
                continue;
            }
            mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j;
            mark[i][j]%=1000;
        }
    }
    int n,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int ans=0;
        for(i=0;i<=n;i++)
            ans+=mark[n][i];
        printf("%d\n",ans%1000);
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#define N 2005
int mark[N][N];
int main()
{
int i,j;
memset(mark,0,sizeof(mark));
for(i=1;i<=2000;i++)
{
  mark[i][1]=1;
  mark[i][0]=0;
  for(j=1;j<=2000;j++)
  {
   if(i==j)
   {
    mark[i][j]=1;
    continue;
   }
   mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j;
   mark[i][j]%=1000;
  }
}
int n,T;
scanf("%d",&T);
while(T--)
{
  scanf("%d",&n);
  int ans=0;
  for(i=0;i<=n;i++)
   ans+=mark[n][i];
  printf("%d\n",ans%1000);
}
return 0;
}

补充：软件开发 , C++ ,