本文主要是介绍Codeforces Round #230 (Div. 2) C. Blocked Points D. Tower of Hanoi，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. Blocked Points 题意：A点和B点是4-connected，的条件是
- the Euclidean distance between A and B is one unit and neither A nor B is blocked;
- or there is some integral point C, such that A is 4-connected with C, and C is 4-connected with B.
这段描述类似递归的意思，就是A 和B 4-connected 就是，A可以通过 非BLOCK的点 延伸到 B点。A B都是非blocked的。
距离 原点 的距离<=N的整数点为special 点，否则 为non-special点。
求 把最少数量的点blocked，使得所有的spe点和non-spe点 都不4-connected.
即 求距离原点的距离<=n的点构成边界，封锁起来。注意特判n==0.详见code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef __int64 LL;
#define INF 1000000000
#define N 80000000
LL n;
int main()
{scanf("%I64d",&n);LL sum=0;LL last=n;LL now;for(LL i=1;i<=n;i++){now= (LL)sqrt(1.0*(n*n-i*i));//printf("%I64d - %I64d\n",i,now);if(last==now) sum++;else{sum+=(last-now);}last=now;}if(!n){printf("1\n"); return 0;}printf("%I64d\n",sum*4);return 0;
}D. Tower of Hanoi
汉诺塔问题，不过不同的柱子之间的移动会有不同的cost，求把N个盘子从第一个移动到第三个，cost的和最小是多少。
DP，记忆化搜索。 dp[n][i][j][k], 代表把n个盘子从i通过j到k。
dp[n][i][j][k]的最优，是以下两种情况的最小者
1，把n-1个从l通过r移到m上，然后把第n个从l移到r上，最后把n-1个从m通过l移到r上。
2，把n-1个从l通过m移到r上，然后把第n个从l移到m上，然后把n-1个从r通过m移到l上，然后把第n个从m移到r上，最后把n-1个从l通过m移到r上。
详见code:#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define INF 1000000000
#define N 45
LL dp[N][5][5][5],n;
LL cost[5][5];
LL dfs(LL nn,LL l,LL m,LL r)
{if(!nn) return 0;if(dp[nn][l][m][r]>=0) return dp[nn][l][m][r];LL m1=dfs(nn-1,l,r,m)+cost[l][r]+dfs(nn-1,m,l,r);LL m2=dfs(nn-1,l,m,r)+cost[l][m]+dfs(nn-1,r,m,l)+cost[m][r]+dfs(nn-1,l,m,r);dp[nn][l][m][r] =min(m1,m2);return dp[nn][l][m][r];
}
int main()
{for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){scanf("%I64d",&cost[i][j]);}}scanf("%I64d",&n);memset(dp,-1,sizeof(dp));printf("%I64d\n",dfs(n,1,2,3));return 0;
}这篇关于Codeforces Round #230 (Div. 2) C. Blocked Points D. Tower of Hanoi的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
