F 过桥

思路 DP 每一格会有正数和负数的情况出现，如果为正数，说明(可能)可以往前面走，如果为负数，说明只能后退

由于我们的目标是走到尽头，那么负数对与前进是没有贡献的，甚至会出现，

1，2，-1，-1，-1，-1，3 这种，负数把路给完全堵死的情况 (遇到负数后退，始终不能到达3 这个正数的点位继续前进)

转移方程

i<j , i+ar[i]<=j

time[j] = min(time[i]+1,time[j]) 意味着，如果可以前进到 J ，那么时间消耗为time[j] 与 time[i]+1 中较小的那个

#include<string>
#include<algorithm>
#include<bits/stdc++.h>

#define For(n) for (int i=0;i<n;i++)


using namespace std;
typedef long long int ll;

int main()
{
	int n;
    cin>>n;
    int ar[2005]={0};
    int time[2005];
    for (int i=0;i<2005;i++)
    {
        time[i]=2005;
    }
    //  将时间先定为 2005，一个常数
    //如果最后 time[n-1] 的时间依然为 2005 ， 说明他没有被修改过，即没有路径能够到达
    //则不能走通，输出 -1
    //否则，time[n-1] 的值被修改过，则说明可以走到头，输出即可
    
    time[0]=0;
    for (int i=0;i<n;i++)cin>>ar[i];

    for (int i=0;i<n;i++)
    {
        if (ar[i]>0)
        //正数才需要考虑，是否会使得后面的路径消耗更小
        //负数直接不管
        {
			for (int j=i+1;j-i<=ar[i] && j<n;j++)
			{
				time[j]=min(time[j],time[i]+1);
			}
        }
    }
    /*
    这是调试用的，可以自己输出，查看具体的 time 
    for (int i=0;i<n;i++)
    {
    	cout<<time[i]<<" ";
	}
	cout<<endl;*/
    
    //最后的答案处理
    if (time[n-1]==2005)
    {
        cout<<-1<<endl;
    }
    else cout<<time[n-1]<<endl;
    return 0;
}

G 空调遥控

思路 题目的关键是 |ar[i]-K|<= P 意味着， 对于 K 温度而言， 可以覆盖的范围在 [-P+K, P+K] 只要ar[i] 落在此范围内即可

我们先将ar[i]出现的次数进行记录 然后按照顺序，进行查找 第一次需要找 0~2P+1 ，记录此时的人数 为 cnt 然后再继续遍历 从 2p+2, 一直到 n , 因为 K 覆盖的范围有限，因此，在增加 ar[i] 的时候，也需要减去之前 ar[i-2*p-1] 的次数

然后依次和 cnt 进行比较即可

#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#define For(n) for (int i=0;i<n;i++)


using namespace std;
typedef long long int ll;


int main()
{
	int n,p;
	int x;
	cin>>n>>p;
	vector<int>ar(n+1);
    
	//memset(ar,0,sizeof(ar));
	For(n)
    {
        cin>>x;
        ar[x]++;
    }//先输入，并将出现次数记录
    
    int ans=0;
    for (int i=0;i<=min(2*p+1,n);i++)
    {
        ans+=ar[i];
    }//计算第一次的答案，从0~2*P+1
    
    int cnt=ans;
    //关键  
    //继续遍历，每次进行增加和删除操作，并记录最多的人数
    for (int i=2*p+2;i<=n;i++)
    {
        cnt+=ar[i];
        cnt-=ar[i-2*p-1];
        ans=ans>cnt? ans:cnt;
    }
    cout<<ans<<endl;
    
    
    
    
	return 0;
}