好久没写动归了……
1## 题目描述
在一个 n * n的平面上，在每一行中有一条线段，第 i$行的线段的左端点是(i, L_{i})，右端点是(i, R_{i})。
你从 (1,1) 点出发，要求沿途走过所有的线段，最终到达 (n,n) 点，且所走的路程长度要尽量短。
更具体一些说，你在任何时候只能选择向下走一步（行数增加 1）、向左走一步（列数减少 1）或是向右走一步（列数增加 1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。
include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int n,ans = 0,l[N],r[N];
int f[N][2];//f[i][j]表示 到第i行，j = 0从左边走，j = 1从右边走
int main()
{
cin>>n;
for(int i = 1;i <= n;i++)
cin>>l[i]>>r[i];
f[1][0] = r[1] - 1;
f[1][1] = r[1] - 1 + r[1] - l[1];
for(int i = 2;i<= n;i++)
{
f[i][0] = min(f[i-1][0] + abs(r[i-1] - l[i]) , f[i-1][1] + abs(l[i-1] - l[i])) + 1 + r[i] - l[i];
f[i][1] = min(f[i-1][0] + abs(r[i-1] - r[i]) , f[i-1][1] + abs(l[i-1] - r[i])) + 1 + r[i] - l[i];
}
cout<<min(f[n][0] + n - r[n], f[n][1] + n - l[n])<<"\n";
return 0;
}
2# [HNOI2004] 打鼹鼠
题目描述
鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 n * n 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 i 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 (i, j) 的网格移向 (i-1, j), (i+1, j), (i, j-1), (i, j+1) 四个网格，机器人不能走出整个 n * n 的网格。游戏开始时，你可以自由选定机器人的初始位置。
现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。
include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int f[N],n,m;//i 表示打到第i个鼹鼠后的最大总个数
struct node{
int t,x,y;
}a[N];
int ans = 0;
int cmp(node xx,node yy)
{
return xx.t < yy.t;
}
bool check(int i,int j)
{
if(abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) <= a[i].t - a[j].t) return 1;
else return 0;
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= m;i++)
cin>>a[i].t>>a[i].x>>a[i].y;
sort(a + 1, a + m + 1, cmp);
for(int i = 1;i <= m;i++)
for(int j = 0;j < i;j++)
{
if(j == 0||check(i , j))
{
if(j == 0) f[i] = max(f[i] , 1);
f[i] = max(f[i] , f[j] + 1);
}
}
int ans = 0;
for(int i = 1;i <= m;i++)
ans = max(ans , f[i]);
cout<<ans<<"\n";
return 0;
}
琪露诺
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为 0 到 N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 i 时，她只移动到区间 [i+L,i+R] 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数 Ai，编号为 0 的格子冰冻指数为 0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 Ai。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号 0 的格子上，只要她下一步的位置编号大于 N 就算到达对岸。
include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n,l,r;
int f[N],a[N];//到达i时的最大距离
int main()
{
cin>>n>>l>>r;
for(int i = 0;i <= n;i++)
cin>>a[i];
f[0] = 0;
for(int i = 1;i < n + r;i++)
{
for(int j = i - r;j <= i - l;j++)
{
f[i] = max(f[i] , f[j] + a[i]);
}
}
int ans = 0;
for(int i = 1;i <= n + r;i++)
cout<<f[i]<<" ";
cout<<"\n";
for(int i = n + 1;i < n + r;i++)
ans = max(ans , f[i]);
cout<<ans<<"\n";
return 0;
}