高度由习惯堆积

分类 OJ:TopCoder 下的文章

February 16, 2019

Topcoder10073 SRM418 BarracksEasy

这题最困难的方面是战斗的策略。假设我们有$i$个士兵,兵营的血量为$z$,我们的对手有$j$个士兵,设$dp[i][j][k]$为我们赢得战斗的最小回合数(如果不可能,则为无穷)。计算时,按照题目的步骤一步步模拟递推就行了。但是如果只是这样的话,可能会出现环,或者无穷的状态(比如$j$不断往上增长),所以为了解决这一点,需要将$j>100$的情况全部舍弃。具体细节请看代码#includ...
February 16, 2019

Topcoder9902 SRM416 DancingCouples

$dp[i][S]$表示选到某个男生,女生的选择集合。然后暴力转移,复杂度$O(2^{n*m}*K*m)$极限数据一亿多,然而卡过去了。#include<bits/stdc++.h> #define clr(x,y) memset(x,y,sizeof(x)) using namespace std; int n,m,ans=0; bool A[15][15]; vector&l...
February 16, 2019

Topcoder8307 SRM390 SetOfPatterns

其实这是一道简单题不知道为什么1AC定义$dp[i][S]$表示前$i$的长度,取了$S$这个集合,这样就可以用$dp[i][S]$更新$dp[i+1][S与v]​$。最后统计一下答案就好了。代码#include<bits/stdc++.h> using namespace std; const int M=1000003; int st,cnt,dp[52][1<<...