网站上做烟花效果,重庆网站维护制作,广东工厂网站建设,哈尔滨做网站电话题目#xff1a;http://www.51nod.com/onlineJudge/questionCode.html#!problemId1250 仔细思考dp。 第一问#xff0c;考虑已知 i-1 个数有多少种方案。再放入一个数#xff0c;它是最大的且在最后面#xff0c;所以它的位置不同的话#xff0c;就是不同的方案。它在特定…题目http://www.51nod.com/onlineJudge/questionCode.html#!problemId1250 仔细思考dp。 第一问考虑已知 i-1 个数有多少种方案。再放入一个数它是最大的且在最后面所以它的位置不同的话就是不同的方案。它在特定的位置其余部分的值就是 i-1 的值。 所以再用前缀和优化成 n^2 即可。k可减任意个2。 第二问还是像上面一样考虑。但新来的数只会和前面的数交换一次。任何一种交换 k ( k1 ) 次的方案都可以转换成前面的数先交换 k-1 次再由新来的数交换一次。所以就能很方便地dp了。 还可以从逆序对的角度考虑第一问、从斯特林数的角度考虑第二问。反正式子是一样的。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int N3005,mod1e97;
int n,k,dp[2][N],c[2][N],ans,u,v;
int main()
{scanf(%d%d,n,k);dp[1][0]1;for(int i0;ik;i) c[1][i]1;u0;v1;for(int i2;in;i){for(int j0;jk;j){dp[u][j](c[v][j]-(j-i0?c[v][j-i]:0)mod)%mod;c[u][j](dp[u][j](j?c[u][j-1]:0))%mod;}u!u;v!v;}for(int ik;i0;i-2) (ansdp[v][i])%mod;printf(%d ,ans); ans0;u0;v1;memset(dp[1],0,sizeof dp[1]); dp[1][0]1;for(int i2;in;i){for(int j0;jk;j)dp[u][j](dp[v][j](j?(ll)dp[v][j-1]*(i-1)%mod:0))%mod;u!u;v!v;}for(int i0;ik;i) (ansdp[v][i])%mod;printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Narh/p/9606366.html
