网上做期末试卷的网站,网上国网app,制作自己网站有什么软件,成都设计院排行E - Alphabet Tiles (atcoder.jp)
题目大意#xff1a;1到k长度的字符串时#xff0c;在A-Z给定数量下#xff0c;搭配出多少种不同的字符串
思路
排列组合#xff0c;会死人的
暴搜#xff1a;可以解决#xff0c;但是时间太长
dp#xff1a;考虑前 i 个字母…E - Alphabet Tiles (atcoder.jp)
题目大意1到k长度的字符串时在A-Z给定数量下搭配出多少种不同的字符串
思路
排列组合会死人的
暴搜可以解决但是时间太长
dp考虑前 i 个字母在长度为 j 下的字符串有多少种情况这是一个背包问题
难点
现在难点就来到了转移函数了
首先 i 可以继承 i-1对于每个字母遍历它的个数t(1到 l 其中 l 是当前遍历的长度与字母个数的最小值)把 j-t的方案数乘以C(j,k) [相当于是分步乘法把没有这个字母下j-t个已排好的位置放入c个当前字母所以乘以“在j个位置下挑c个位置用组合数”]
难点二初始值把dp[0][0] 和 dp[i][0] 都置为1情况数为1
#includebits/stdc.h
using namespace std;
#define ll long longll dp[30][1005];
ll C[1005][1005];
const int N 998244353;int main()
{int k;cin k;for(int i 0 ; i k ; i){C[i][0] 1;for(int j 1 ; j i ; j){C[i][j] C[i-1][j] C[i-1][j-1];C[i][j] % N; }}dp[0][0] 1;for(int i 1 ; i 26 ; i){int c;cin c;dp[i][0] 1;for(int j 1 ; j k ; j){for(int l 0 ; l min(j,c) ; l){dp[i][j] dp[i][j] dp[i-1][j-l]*C[j][l]%N; //加上使用字母0次、1次、2次的情况 dp[i][j] % N; }}}ll ans 0;for(int i 1 ; i k ; i){ans dp[26][i];ans % N; }cout ans;return 0;
}
反思
转移函数除了考虑从哪里转来还要考虑自身的结果是怎么计算的满足题意不重不漏用在本题里就是每个长度的串考虑用上0个、1个、2个当前字母还要考虑自身会被哪些值在遍历时影响到或有多次赋值思考如何保证值在被累加或是其它积累。
