A49759. 题目的分数值程序命名：score.cpp
填空题
中等
知识点
题目描述
题目的分数值
程序命名：score.cpp
题目描述：
有n个问题，现在请你给这n个问题分配分值。
n个问题已经按从简单到困难排好序，第i个问题的分值是Ai，n个问题的分值满足如下关系：1<=A1<=A2<=.......<=An<=n。不同的问题可以具有相同的分值。
主办方希望：解决更多问题的参赛者的排名更高。因此，对于任何解决了k（1 <=k<=n-1）个问题的参赛者，其分数总和一定要小于解决了任何k+1个问题的参赛者的分数总和。
你有几种分配分值的方法？将答案对素数m取余后输出。
输入：
整数n和m
其中2<=n<=5000，9x10^8<m<10^9，m为素数。
输出：
分值分配的方案数对m取余后的数字
样例输入1：
2 998244353
样例输出1：
3
样例1说明：
2个题的分值分配有3种方案：（1，1），（1，2），（2，2）。
样例输入2：
3 998244353
样例输出2：
7
样例2说明：
3个题的分值分配有7种方案：（1，1，1），（1，2，2），（1，3，3），（2，2，2），（2，2，3），（2，3，3），（3，3，3）
参考答案
//动态规划题
#include<iostream>
#include<iomanip>
using namespace std;
int dp[502][502];
int main()
{
int n,m;
cin>>n>>m;
for(int k=1;k<=n;k++) dp[1][k] = k;
for(int i=2;i<=n;i++) // 后面还有几个数
{
for(int k=1;k<=n;k++) //当前阶段有多少种选择
{
if(k==1) dp[i][k] = dp[i-1][k];
else dp[i][k] =(dp[i][k-1] + dp[i-1][k]) % m;
}
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
int k1= min(i,n-j+1);
ans = (ans + dp[n-2][k1]) % m;
}
}
if(n==2) ans = 3;
cout<<ans<<endl;
return 0;
}
上一题
下一题