A： 题意：给你一个半径为n的圆 求最少阻塞多少个点 才能使所以圆内及圆上的点 都不与外边的点相连 相连是距离为1 只算整数点
这题定住x，y依次递减 判断一下是否4-connect 这个意思就是 它上下左右有没有跟它相连的 圆是对称的 判断1/4圆就可以了
像左边的部分图 令初始y为n 只需要判断它的左上有没有跟它连接的就可以了 如果左边有的 话 y就减一 因为说明(i+1,y)已经不在圆内了 ，这里枚举的是圆内的点有没有跟圆外的点相连接
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 using namespace std; 10 #define LL long long 11 int main() 12 { 13 LL n,i,j; 14 while(cin>>n) 15 { 16 LL s=0; 17 if(n==0) 18 { 19 puts("1"); 20 continue; 21 } 22 j = n; 23 for(i = 0; i < n ;i++) 24 { 25 while((i+1)*(i+1)+j*j>n*n) 26 { 27 j--; 28 s++; 29 } 30 if((j+1)*(j+1)+i*i>n*n) s++; 31 } 32 cout<<s*4<<endl; 33 } 34 return 0; 35 }
B：题意：类似于汉诺塔 只不过加了每次挪动所需要的费用
可以递推出来 dp[i][j][g] = min(dp[i-1][j][v]+p[j][g]+dp[i-1][v][g],dp[i-1][j][g]*2+p[j][v]+dp[i-1][g][j]+p[v][g]) dp[i][j][g]表示把i个盘子从j移到G
这一长串的公式就是汉诺塔的移法 只不过不是最少的步骤了 一种是把i-1个盘子从1移到2，把第i个盘子从1移到3，把i-1个盘子再从2移到3，Ok.
第二种是 把第i-1个盘子从1移到3，把第i个盘子从1移到2，再把i-1个盘子从3移到1，再把第i个盘子从2移到3，最后把i-1个盘子从1移到3.
这两种方法取一个最优的。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 #define LL long long 10 #define INF 1e17 11 LL dp[45][4][4]; 12 int a[4][4]; 13 int main() 14 { 15 int i,j,n,g; 16 for(i = 1; i <= 3 ; i++) 17 for(j = 1; j <= 3; j++) 18 cin>>a[i][j]; 19 cin>>n; 20 for(i = 0; i <= n ;i++) 21 for(j = 1; j <= 3 ; j++) 22 for(g = 1; g <= 3 ; g++) 23 if(i==0) dp[i][j][g] = 0; 24 else 25 dp[i][j][g] = INF; 26 int v; 27 for(i = 1; i <= n ; i++) 28 { 29 for(j = 1 ; j <= 3 ; j++) 30 for(g = 1; g <= 3 ; g++) 31 { 32 if(j==g) continue; 33 for(int e = 1 ; e <= 3 ; e++) 34 if(e!=j&&e!=g) {v = e;break;} 35 dp[i][j][g] = min(dp[i-1][j][v]+a[j][g]+dp[i-1][v][g],2*dp[i-1][j][g]+a[j][v]+dp[i-1][g][j]+a[v][g]); 36 } 37 } 38 cout<<dp[n][1][3]<<endl; 39 return 0; 40 }