P2039 [AHOI2009] 跳棋
题目描述
在一个111行NNN列（NNN是奇数）的棋盘上，有KKK个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。
请回答以下两个问题：
- 移动开始前至少要放多少棋子才能完成任务。
- 如果要使开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。
关于规则的补充说明：
- 只能往空位上放棋子，不管是移动开始前还是移动过程中。
- 移动前棋盘最左端的那个原始棋子绝对不能被吃掉。
输入格式
第一行一个正奇数NNN。
第二行有NNN个整数，如果第iii个整数是111，说明第iii个格子是红色格子，否则为白色格子。
数字间用空格分开。
输出格式
两行，每行一个整数分别代表第一问和第二问的结果。
输入输出样例 #1
输入 #1
5 0 0 0 1 0输出 #1
1 1说明/提示
在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动第三格的棋子把它吃掉，从而达到终点。
100%100\%100%的数据中，1≤N≤10001\le N\le 10001≤N≤1000，输出中的数字不超过101510^ {15}1015。
30%30\%30%的数据中，N≤20N\le 20N≤20。
Source: [Ahoi2009] checker
C++实现
#include<stdio.h>#include<stdlib.h>#definemaxn1005#defineINF1e18#defineLLlonglongLL n,q[maxn],num[2];LL dp[maxn];LLmin(LL a,LL b){returna<b?a:b;}voidprint(boolflag){//输出函数if(!flag){printf("%lld\n%lld",num[0],num[1]);exit(0);//直接结束程序}LL ans=0;for(inti=1;i<=n;i++)ans+=(i%2)?0:dp[i];//只有偶数点才计入答案printf("%d\n%lld",0,ans);}intmain(){boolflag=false;scanf("%lld",&n);for(LL i=1;i<=n;i++){scanf("%lld",&q[i]);if(i==1){q[i]=0;//起点的红点没有用，故赋值为 0，作为白点处理continue;}if(i%2==0)num[q[i]]++;if(q[i]&&q[i-1])flag=true;}for(inti=1;i<=n;i++)dp[i]=q[i]?1:INF;for(inti=3;i<=n;i++)if(q[i]&&q[i-1]){for(intj=i-2;j>=1;j--)dp[j]=min(dp[j],dp[j+1]+dp[j+2]);//跳棋向左边跳for(intj=i+1;j<=n;j++)dp[j]=min(dp[j],dp[j-1]+dp[j-2]);//跳棋向右边跳}print(flag);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
