T1

70%算法

定义f[i][j]表示枚举到i位置，已经使用过了j个队，

$f[i][j]+=f[i-1][t] ( t \in [max(0,j-k),j])$滚动一下

这是个O(n^3)的，考虑如何优化，发现可以使用前缀和，避免枚举t，$O(n^2)$

100%算法

问题转化成：m个物品，放到n个抽屉里，每个至少放一个，最多放k个

若任何的限制: C(m+n-1,n-1)表示一共有m个物品，分成n组就要用n-1个挡板，把挡板也看成空位，总共m+n-1个空位，选出来n-1个

若考虑至少放一个：C(m-n+n-1,n-1)先用n个物品给每个抽屉放一个，剩了m-n个物品，再加上n-1个空，剩下的同上

再考虑k的限制：C(n,i)*C(m-n-i*k+n-1,n-1)表示至少有i个的数量已经超过k(>=k+1)所以先给n个抽屉放一个之后，再给n个放上k个，使之成为k+1个

就是m-n-i*k，再加上n-1个空

数组开2e7就行，显然n>m直接return0

T2

对于无环的情况，最优解就是，图中的最长链的长度，，，为什么？

注意审题：只是炸城市，道路不炸，故城市毁了，其他城市的联通性不变，所以最长链上最少要炸的次数就是链长，而其他的路径，当然可以在炸最长链上的每个节点的同时也一起炸