nefu 406

本文主要是介绍nefu 406，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.nefu.edu.cn/JudgeOnline/problem/406.jsp

这题真心坑呀!开始数组开小了，死活TLE，不知道怎么改了。之后改过来之后，就wa，后来看了标称才恍然大悟，哎……dp[ i ][ j ] 表示长度为用前i中颜色组成长度为j的串的个数

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;const long long mod=1000000007;
int color[10010],num[1010];
long long dp[1010][210];
long long c[210][210];int main(int argc, char *argv[])
{int n,k,a;c[0][0]=1;c[1][0]=c[1][1]=1;for(int i=2;i<=200;i++){c[i][0]=c[i][i]=1;        for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}while(scanf("%d%d",&n,&k)==2){int Max=0;for(int i=0;i<n;i++)                             scanf("%d",&color[i]),Max=max(Max,color[i]);memset(num,0,sizeof(num));  for(int i=0;i<n;i++)  {scanf("%d",&a);if(a) num[color[i]]++;}int tt=0;for(int i=0;i<=Max;i++)if(num[i]!=0)num[++tt]=num[i];memset(dp,0,sizeof(dp));for(int i=0;i<=tt;i++)dp[i][0]=1;for(int i=0;i<tt;i++){     for(int j=1;j<=k;j++)    dp[i+1][j]+=dp[i][j];for(int j=0;j<=k;j++)if(dp[i][j])for(int d=1;d<=num[i+1]&&d+j<=k;d++)dp[i+1][d+j]=(dp[i+1][d+j]+dp[i][j]*c[d+j][d]%mod)%mod;}/* long long ans=0;for(int i=0;i<=tt;i++)ans=(ans+dp[i][k])%mod;*/printf("%lld\n",dp[tt][k]);  }//system("PAUSE");return EXIT_SUCCESS;
}

这篇关于nefu 406的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---