贪心算法+dp+最短路+搜索+差分+二维前缀和题组_贪心算法解二维下料问题

[P2242 公路维修问题]

题解：可用贪心思想

题目要求实施交通管制的路段总长度最短，我们就必须使管制的路段中被浪费的长度尽量小。因为只有坑所在的点才需要被维护，这里“被浪费的长度”，其实就是坑与坑之间的距离 ，即没有被管制的路段。

显然可以得出结论： 所有被管制路段的的开头和结尾一定都在坑上， 才能使浪费达到最小。所以我们需要考虑的其实是从第一个坑到第n个坑的范围，道路的头尾两端都可以省略。

那么问题就来了，在怎么在第一个坑和最后一个坑之间管制m个路段，使总浪费最小呢？

我们可以注意到，根据刚才得出的结论，在这m条路段中，第一条的开头一定是第一个坑，而第m条路段的结尾一定是第n个坑。每两个管制路段之间会有一个没有被管制的路段，所以，在第一个坑和第n个坑之间，一共会有m-1个没有被管制的路段，即会有m-1个“坑与坑之间的距离”会被浪费。

为了使浪费最短，我们就可以用sort对每两个坑之间的距离进行排序，然后用第一个坑到第n个坑之间的距离依次减去前m-1个最短的浪费长度（两个坑之间的距离），就可以求出答案了。

#include <bits/stdc++.h>
using namespace std;
int a[15001],b[15001],ans;
bool compare(int a,int b){
    return a>b;
}
int main(){
   int n,m;
   cin>>n>>m;
   for(int i=1;i<=n;i++)cin>>a[i];
   ans=a[n]-a[1]+1;
   for(int i=1;i<n;i++){
     b[i]=a[i+1]-a[i];
   }
   sort(b+1,b+n,compare);
   for(int i=1;i<=m-1;i++){
      ans=ans-b[i]+1;
   }
   cout<<ans;
   return 0;
}

[P6023 走路]

题解：这题还是贪心思想，并且题目中有句非常重要的话：“如果你第 p 天走完了 q 步，那么第 p 天中接下来的每一步都会给你加 1 积分”，仔细看这里说的是 在第p 天这一天中接下来的每一步，第p+1天的每一步是不能享受到第p天的激励机制的。所以本题的核心是把所有步数集中到一天，这样可以叠加的积分就不会被浪费了，然后取个最大的即可

#include <bits/stdc++.h>
using namespace std;
long long nums[100001];
long long n,ans;
int m,k;
int main()
{
 
    cin>>n>>m>>k;
    for(int i=1; i<=k; i++)
    {
        long long p,q;
        cin>>p>>q;
        if(n>q)
        {
            nums[p]+=(n-q);
        }
    }
    for(int i=1; i<=m; i++)
    {
        ans=max(ans,nums[i]);
    }
    cout<<ans;
    return 0;
}

[P1176 路径计数2]

题解：这题是一个dp问题，因为a[i][j]可以走到a[i+1][j]和a[i][j+1]，所以a[i][j]可以由a[i-1][j]和a[i][j-1]走到。所以状态转移方程为a[i][j]=a[i-1][j]+a[i][j-1]

#include <bits/stdc++.h>
using namespace std;
int n,m;
int vis[1001][1001],book[1001][1001];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        book[x][y]=1;//不能走
    }
    vis[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(book[i][j]==1)vis[i][j]=0;
            else{
                vis[i][j]+=vis[i-1][j]+vis[i][j-1];
                vis[i][j]%=100003;
            }
        }
    }
    cout<<vis[n][n];
    return 0;
}

[P1119 灾后重建]

题解：这题很明显是求多源最短路径，再加上题目保证所有的数据都是用时间顺序给出的，我们可以想到使用Floyd算法来解决。我们可以按照时间顺序更新每一个可用的点（即修好的村庄），将该点加入中转站中，更新任意两个村庄的距离。如果有不懂的可以去理解一下Floyd算法第一重循环的意义。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,m,now;
int fixTime[201];
int dis[201][201];
void update(int k)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(dis[i][j]>dis[i][k]+dis[k][j])
            {
                dis[i][j]=dis[i][k]+dis[k][j];
                dis[j][i]=dis[i][k]+dis[k][j];
            }
        }
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)cin>>fixTime[i];
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i==j)dis[i][j]=0;
            else dis[i][j]=inf;
        }
    }
    for(int i=0; i<m; i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        if(t<dis[x][y])
        {
            dis[x][y]=t;
            dis[y][x]=t;
        }
    }
    int q;
    cin>>q;
    for(int i=0; i<q; i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        while(fixTime[now]<=t&&now<n){
            update(now);
            now++;
        }
        if(fixTime[x]>t||fixTime[y]>t)cout<<-1<<endl;//村庄还未建好
        else{
            if(dis[x][y]==inf)cout<<-1<<endl;
            else cout<<dis[x][y]<<endl;
        }
    }
    return 0;
}

[P3395 路障]

题解：这道题纯纯的bfs搜索题，需要注意的就是book数组需要把障碍地方也打上标记，然后就是每组测试数据注意初始化

#include <bits/stdc++.h>
using namespace std;
int t,n,flag,nowTime;
int nextt[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
struct Node
{
    int x,y;
} mapp[10000010];//这里需要开大一点
int book[1001][1001];
void bfs()
{
    queue<Node>q;
    q.push({1,1});
    nowTime=0;//初始化
    while(!q.empty())
    {
        Node temp=q.front();//取出队头元素
        q.pop();//出队
        int x=temp.x,y=temp.y;
        if(x==n&&y==n)
        {
            flag=1;
            break;
        }
 
        for(int i=0; i<4; i++)
        {
            int dx=x+nextt[i][0];
            int dy=y+nextt[i][1];
            if(dx>=1&&dy>=1&&dx<=n&&dy<=n&&book[dx][dy]==0)
            {
                book[dx][dy]=1;
                q.push({dx,dy});
            }
        }
        nowTime++;
        book[mapp[nowTime].x][mapp[nowTime].y]=1;//把障碍地方也要标记起来
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1; i<=2*n-2; i++)
        {
            cin>>mapp[i].x>>mapp[i].y;
        }
        book[1][1]=1;
        bfs();
        if(flag==1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        //初始化
        memset(book,0,sizeof(book));
        flag=0;
    }
    return 0;
}

[P1907 设计道路]

题解：这题明显是求最短路，很明显想到迪杰斯特拉算法，并且这题不用堆优化。我们把 0 号点作为码头，把 n+1 号点设为最后要到达的地方（家），所以这题最终求的就是 0 号点到 n+1 号点的最短路。题目给了路口(可以看做图的顶点)，Rome Road会由题目给出，其他的边也就是Dirt Road则需要用两点间距离公式算出来，并且所有边都是双向的，建好图后就是正常的迪杰斯特拉算法了。

#include<bits/stdc++.h>
using namespace std;
double dirtRoad,romeRoad;
double xx[1010],yy[1010];
double mapp[1010][1010];
double dis[1010];
bool book[1010],edge[1010][1010];
int n;
double getDistance(double x1,double y1,double x2,double y2)
{
    double distance=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    return distance;
}
void dij()
{
    for(int i=1; i<=n+1; i++)
    {
        int t=-1;
        for(int j=0; j<=n+1; j++)
        {
            if(book[j]==false&&(t==-1||dis[t]>dis[j]))
            {
                t=j;
            }
        }
        book[t]=true;
        for(int j=0; j<=n+1; j++) //更新与u相连点的dis[]
        {
            if(dis[j]>dis[t]+mapp[t][j])dis[j]=dis[t]+mapp[t][j];
        }
 
    }
}
int main()
{
    cin>>dirtRoad>>romeRoad;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>xx[i]>>yy[i];
    }
    int a,b;
    cin>>a>>b;
    while(a!=0&&b!=0)
    {
        edge[a][b]=edge[b][a]=true;
        mapp[a][b]=mapp[b][a]=getDistance(xx[a],yy[a],xx[b],yy[b])*romeRoad;
        cin>>a>>b;
    }
    cin>>xx[0]>>yy[0]>>xx[n+1]>>yy[n+1];
    for(int i=0; i<=n+1; i++)
    {
        for(int j=0; j<=i; j++)
        {
            if(!edge[i][j])
            {
                mapp[i][j]=mapp[j][i]=dirtRoad*getDistance(xx[i],yy[i],xx[j],yy[j]);
            }
        }
    }
    //初始化
    for(int i=1; i<=n+1; i++)dis[i]=mapp[0][i];
    dis[0]=0;
    book[0]=1;
    dij();
    printf("%.4lf",dis[n+1]);
    return 0;
}

[P4552 IncDec Sequence]

题解：像这种多次选择一个区间[l,r]，然后对其进行加减操作，让我们求最后的结果数组的都可以试着用差分思想来做。

差分的概念是b[1]=a[1]，b[i]=a[i]-a[i-1]，

简单来说就是两个数的差。b[1]一定是等于a[1]的，因为b[1]=a[1]-a[0]，而

a[0]=0,所以b[1]=a[1]。

了解了概念，我们看一下差分和原序列之间有什么关系

把序列a的区间[l,r]+d（或者说a[l]+d,a[l+1]+d,a[l+2]+d+....+a[r]+d的

话，那么这个序列a的差分序列b的变化就为b[l]+d,b[r+1]-d

如果a[l,r]-1，则b[l]-1，b[r+1]+1;

如果a[l,n]+1(l <= n - 1)，则b[l]+1，其余不变，因为b[n+1]已越界无意义

如果a[l,n]-1(l <= n - 1),则b[l]-1，其余不变，因为b[n+1]已越界无意义

补充有关差分的学习链接:一维差分_哔哩哔哩_bilibili

-------------------------------------------------------------------------------------------------------------------------

下面看一下这个题该怎么做

要使得序列的数全部相等，其实就是让他们之间的差全为0，也就是差分序列的除了第

一项每一项都是0，为什么除了第一项呢，因为b[1]=a[1]-a[0]，而a[1]是开头的数

我们把问题转化成了让差分序列除第一项全等于0：

我们优先对这个正数和负数进行操作，因为我们有以下两个公式

如果a[l,r]+1，则b[l]+1，b[r+1]-1

如果a[l,r]-1，则b[l]-1，b[r+1]+1

正数-1，负数+1，这样相当于一步里作用了两步，比让正数一个个-1和让负数一个个

+1快多了

那么我们可以进行多少种这样的操作呢？

我们可以令差分序列里正数绝对值的总和为p，负数绝对值总和为q

可以进行这样一步顶两步的操作就是min（p，q），因为这种操作正数负数是一一配

对的，当少的那个先用完了，剩下的没有可以配对的了，只能一步步减或一步步加。

所以我们总共要进行的操作就为min（p，q）+abs（p-q），也就是max（p，q）

-------------------------------------------------------------------------------------------------------------------------

第一问完成，看第二问保证最少次数的前提下，最终得到的数列有多少种？

得到的数列有多少种，其实就是问的b[1]可以有多少种

我们上述所有操作是与b[1]无关的，因为我们的目标是让除了b[1]以外的项变0，所

以我们上述的操作没有考虑到b[1]，b[1]怎么变，与我们求出的最小步骤无关

那么，我们怎么知道b[1]有几种呢？

很简单，其实就是看看有几种一步步减或一步步加的操作数，有几步一步步的操作就有几种情况+1，为什么+1呢，因为这个b[1]本身就有一个值，就算你不对他进行任何操作，它自己也有一种情况。那么一步步的操作数就为abs (p-q)，最后结果为abs (p-q)+1

#include<bits/stdc++.h>
using namespace std;
int n;
long long vis[100010],temp,correct,negative;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>vis[i];
    }
    for(int i=2;i<=n;i++){
        temp=vis[i]-vis[i-1];
        if(temp>0)correct+=temp;
        else negative-=temp;
    }
    long long ans1=max(correct,negative);
    long long ans2=abs(correct-negative)+1;
   cout<<ans1<<endl<<ans2;
    return 0;
}

[P2004 领地选择]

题解：题意大概是说 n×m 的矩形中找到一个边长为 c 的矩形使它的价值最大。根据题意，我们可以枚举左上角的坐标，利用边长 c 算出左下、右上、右下角。至于求和部分可以利用二维前缀和算法做出预处理，取其中最大值的左上角坐标即可。

补充二维前缀和的学习链接:二维前缀和_哔哩哔哩_bilibili

#include<bits/stdc++.h>
using namespace std;
int n,m,c,maxx=-999999999,ansx,ansy;//maxx不能取0，因为不是最小的
int g[1001][1001],sum[1001][1001];
int get_sum(int x1,int y1,int x2,int y2){
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
int main()
{
    cin>>n>>m>>c;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>g[i][j];
            sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
    }
    for(int i=1;i<=n-c+1;i++){
        for(int j=1;j<=m-c+1;j++){//枚举左上角
            int i2=i+c-1;
            int j2=j+c-1;  //计算右下角
            if(maxx<get_sum(i,j,i2,j2)){
                maxx=get_sum(i,j,i2,j2);
                ansx=i;
                ansy=j;
            }
        }
    }
    cout<<ansx<<" "<<ansy;
    return 0;
}