A
只有3种情况:200以上的单独装,3个100的装一起,某两个u,v装一起且u+v<=300,
所以做法是从大到小判断每个大小的最大能与它装一起的是谁,最后剩下100的特判.
B
第一轮如果未分出胜负,考虑一种情况:
mov1 >= mov2, 先手至少不会输.
再判断赢的条件, 设d=mov1-mov2, 先手每一轮结束后可以保证每次距离缩短[1,d],但同时
先手要保持一个安全距离safe以保证不会被后手反击:
safe >= mov2+rng2,
所以当 safe + mov2 <= mov1+d时先手必胜,否则平局.
后手的推理类似.
string FoxAndFencing::WhoCanWin(int m1, int m2, int r1, int r2, int d)
{
if (d<=r1+m1) return "Ciel";
else if (d+m1<=r2+m2) return "Liss";
else if (m2==m1) return "Draw";
else if (m1>m2)
{
if (r1+m1-*m2>r2) return "Ciel";
else return "Draw";
}else
{
printf("%d+%d , %d\n",r2,m2,r1);
if (r2+m2-*m1>r1) return "Liss";
else return "Draw";
}
}
C
首先发现一个性质: 如果某节点x有cnt个孩子,那么往下递归至少有cnt-1个子树存在标记,
这样才能保证x的子树都被识别,根据这条性质设计dp[i][0/1]即可.
但是仅仅这样dp会发现最后结果有一条从根到某叶子的未被标记的链,这条链的某些点可能不会被识别,
为了修正这个问题,可以强制根被标记,换句话说,可以枚举某个被标记的点为根.
#define maxn 51
class TPS {
public:
int minimalBeacons(vector <string>);
};
int dp[maxn][],n,cnts[maxn];
int dfs(int cur,int must,int fa,vector<string> e)
{
int sum=,tmp,res;
if (dp[cur][must]!=-) return dp[cur][must];
if (cnts[cur]==) return dp[cur][must]=must;
for (int i= ; i<n ; i++ ) if (e[cur][i]=='Y' && i!=fa)
sum += dfs(i,,cur,e);
tmp=sum;
for (int i= ; i<n ; i++ ) if(e[cur][i]=='Y' && i!=fa)
tmp = min(tmp,sum-dp[i][]+dfs(i,,cur,e));
if (must && cnts[cur]==) res = sum;
else res = tmp;
if (fa==-) res++;
return dp[cur][must]=res;
}
void initson(int cur,int fa,vector<string> e)
{
for (int i= ; i<n ; i++ )
if (e[cur][i]=='Y' && i!=fa)
{
cnts[cur]++;
initson(i,cur,e);
}
}
int TPS::minimalBeacons(vector <string> e)
{
n = e.size();
int ans = n;
for (int i= ; i<n ; i++ )
{
memset(dp,-,sizeof(dp));
memset(cnts,,sizeof(cnts));
initson(i,-,e);
ans = min(ans,dfs(i,,-,e));
}
return ans;
}