张家港网站建设培训班赣州seo优化

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 

#include<bits/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个当前字母），还要考虑自身会被哪些值在遍历时影响到，或有多次赋值，思考如何保证值在被累加或是其它积累。