洛谷 P1350 车的放置

　　　　　　　　　　　　　　洛谷 P1350 车的放置　　　　

题目描述

有下面这样的一个网格棋盘，a，b，c，d表示了对应边长度，也就是对应格子数。

当a=b=c=d=2时，对应下面这样一个棋盘

要在这个棋盘上放K个相互不攻击的车，也就是这K个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。同样只需要输出答案mod 100003后的结果。

输入输出格式

输入格式：

输入文件place.in的第1行为有5个非负整数a, b, c, d和k。

输出格式：

输出文件place.out包括1个正整数，为答案mod 100003后的结果。

输入输出样例

输入样例#1：

2 2 2 2 2

输出样例#1：

说明

【数据规模与约定】

对于部分数据，有b = 0；

对于部分数据，有a，b，c，d≤4。

对于100%的数据，a，b，c，d，k≤1000，且保证了至少有一种可行方案。

题解：

f[j][i]=(f[j-1][i]+f[j-1][i-1]*(v[j]-i+1))%MOD;

因为题目里提到最终数据要模去100003

所以定义MOD为100003了。

以下代码

 #include<cstdio>

 const int N=;

 const int MOD=;

 int f[N][N],v[N];

 int x,y,z,k,m,ans;

 inline int read() {

     char c=getchar();

     int f=,x=;

     while(c<''||c>'')    {

         if(c=='-')    f=-;

         c=getchar();

     }

     while(c>=''&&c<='')

         x=x*+c-,c=getchar();

     return x*f;

 }

 void print (int x) {

     if(x<) {

         putchar('-');

         x=-x;

     }

     if(x>) {

         print(x/);

     }

     putchar(x%+'');

 }

 int main() {

 //    x=y=z=k=m=read();

     scanf("%d%d%d%d%d",&x,&y,&z,&k,&m);

     for(int i=; i<=z; i++) v[i]=k,f[i][]=;

     for(int i=; i<=x; i++) v[z+i]=k+y,f[z+i][]=;

     f[][]=;

     for(int j=; j<=x+z; j++)

         for(int i=; i<=m; i++)

             f[j][i]=(f[j-][i]+f[j-][i-]*(v[j]-i+))%MOD;

     ans=f[x+z][m];

 //    print(ans);

     printf("%d",ans);

     return ;

 }

不知道为什么，加了读入优化和输出优化，虽然过样例是没问题的，但是在提交的时候不是re就是wa。

然后我把读入输出优化去掉，还故意把数组弄小了，都比之前数组开大了得分高!

所以肯定是优化的原因啊！

一世安宁

巴特西

洛谷 P1350 车的放置

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章