洛谷P2837晚餐队列安排
【洛谷P2837晚餐队列安排】题目中文，不再赘述
思路：我们定义一个数组f[i][j],第二维只有两种情况1/0,表示这位变成1还是2，然后我们考虑一下情况
1.当前位一开始是1，那么考虑两种情况上一位是1，这位不变，那么f[i][0]=f[i-1][0];
第二种这位变成2，那么转移就是上一位是1还是2的最小值+1，f[i][1]=min(f[i-1][0],f[i-1][1])+1
2,当前位一开始是2，那么考虑上一位是2还是1时取最小，这位不变，那么f[i][1]=min(f[i-1][1],f[i-1][0]);
第二种是上一位是一，这一位变成1，那么f[i][0]=f[i-1][0]+1
代码
#include
#include
#include
#include
#include
using namespace std;
const int M=30050;
int n;
int now[M];
int f[M][3];
int main()
{
scanf("%d",&n);
for (int i=1;
i<=n;
i++)
scanf("%d",&now[i]);
f[1][now[1]-1]=0;
f[1][2-now[1]]=1;
for (int i=2;
i<=n;
i++)
{
if (now[i]==1)
{
f[i][0]=f[i-1][0];
f[i][1]=min(f[i-1][0],f[i-1][1])+1;
}
else
{
f[i][0]=f[i-1][0]+1;
f[i][1]=min(f[i-1][0],f[i-1][1]);
}
}
cout< 推荐阅读
- 写在期末考试后
- 最后一顿晚餐
- 愉快的晚餐
- 洛谷 P5056 【模板】插头dp
- C++|【暖*墟】 #洛谷省选网课# 8.1数论进阶
- 洛谷|洛谷 P1481 魔族密码
- SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)
- KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）
- JSOI2018冬令营游记&总结（迁移自洛谷博客）
- 洛谷P5471 NOI2019弹跳