A：水温

知识点：贪心

思路：其实调水温的操作可以看出：将序列分为若干段，使得：

• 第一段的 s+∑xi 在 [L,R] 内。
• 之后每一段 xi 前缀和的极差不大于 R−L+1。

考虑贪心分段，每次都尽量往后推，直到不分段就导致不合法时再分段即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,s,L,R,ans;
struct node{
    int t,x;//在t时刻水温变化x 
}a[100001];
bool cmp(node a,node b){
    return a.t<b.t;//按照时间顺序排序 
}
signed main(){
    cin>>n>>s>>L>>R;
    for(int i=1;i<=n;i++){
        cin>>a[i].t>>a[i].x;
    }
    sort(a+1,a+1+n,cmp);
    int c=R-L+1;//温度差不能超过c 
    for(int i=1;i<=n;i++){
        if(a[i].t==a[i+1].t){//同一时刻温度的变化可以后续累加 
            a[i+1].x+=a[i].x;
            continue; 
        }
        s+=a[i].x;
        if(ans==0){//第一次 
            if(s<L||s>R){
                L=R=s;
                ans++;
                continue;
            } 
        }
        L=min(s,L),R=max(s,R);
        if(R-L+1>c){
            ans++;L=R=s;
        }
    } 
    cout<<ans;
    return 0;
}

B：打鼹鼠

知识点：贪心、动态规划

思路：首先时间是按照升序给出的，所以运用最长不下降子序列求解的思想，枚举 i 前面的每一只鼹鼠，如果可以从第 j 只鼹鼠的位置走到第 i 只鼹鼠的位置，那么就可以把第 i 只鼹鼠接到以第 j 只鼹鼠结尾的打鼹鼠序列上去，更新 ma。

那么怎样判断是否可以从第 j 只鼹鼠的位置走到第 i 只鼹鼠的位置呢？由于机器人不能斜着走，所以两只鼹鼠之间的距离就是 $∣x_i−x_j∣+∣y_i−y_j∣$。如果两只鼹鼠之间的距离小于等于 $t_i−t_j$，那么就走得到，反之就走不到。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct node{
    int t,x,y,num=1;
}a[1001];
int main(){
    freopen("da.in","r",stdin);
    freopen("da.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].t>>a[i].x>>a[i].y;
        int ma=0;
        for(int j=1;j<i;j++){
            if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=a[i].t-a[j].t){
                ma=max(ma,a[j].num);
            }
        }
        a[i].num+=ma;
        ans=max(ans,a[i].num);
    }
    cout<<ans;
    return 0;
}

C：三角形牧场

知识点：动态规划

思路：

首先考虑到dp[k][i][j]:表示用前k个木板是否能围成边长为i,j的三角形 
1、把第k个木板放在第i这条边里，那需要用前k-1个木板围成i-a[k]和j的三角形 dp[k-1][i-a[k]][j]
2、把第k个木板放在第j这条边里，那就需要用前k-1个木板围成i和j-a[k]的三角形 dp[k-1][i][j-a[k]]
3、把第k个木板放在第三条边中，那就需要用前k-1个木板围成i和j的三角形 dp[k-1][i][j] 
dp[k][i][j]=dp[k-1][i-a[k]][j]||dp[k-1][i][ja[k]]||dp[k-1][i][j] 
最后再次枚举每三条边的长度，看看符合三角形边长两边之和大于第三边，若满足，则求出最大值。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[55],s;
double ans=-1;
bool dp[888][888]={1};
int main(){
    freopen("san.in","r",stdin);
    freopen("san.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s+=a[i];//求周长 
    }
    for(int k=1;k<=n;k++){
        for(int i=s/2;i>=0;i--){
            for(int j=s/2;j>=0;j--){
                if(i-a[k]>=0&&dp[i-a[k]][j])dp[i][j]=1;
                if(j-a[k]>=0&&dp[i][j-a[k]])dp[i][j]=1;
            }
        }
    } 
    for(int i=s/2;i>0;i--){
        for(int j=s/2;j>0;j--){
            int k=s-i-j;
            if(!dp[i][j]||!(i+j>k&&i+k>j&&j+k>i)) continue;
            double p=s/2.0;
            ans=max(ans,sqrt(p*(p-i)*(p-j)*(p-(s-i-j))));
        }
    }
    if(ans!=-1)cout<<(long long)(ans*100);
    else cout<<ans;
    return 0;
}

D：两条道路

知识点：树形结构

思路：要先编出两条路径之积，就得先编出一条最长路径的方法，很显然是树的直径。 这时候我们就要想了，如果是两棵树，我们就可求出结果。 对了，我们可以暴力每一条边，在建树时删去这条边，从而建成两棵树。 建出两棵树后，我们就可以做两次树的直径，求出两条路径之长，从而算出结果。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,x[201],y[201],dp[201],s,sum,ans;
vector<int> v[201]; 
void dfs(int f,int p){
    for(int i=0;i<v[f].size();i++){
        int g=v[f][i];
        if(g==p)continue;
        dfs(g,f);
        sum=max(sum,dp[f]+dp[g]+1);
        dp[f]=max(dp[f],dp[g]+1); 
    }
} 
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x[i]>>y[i];
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }//断开第i条边看看 
    for(int i=1;i<n;i++){
        memset(dp,0,sizeof dp);
        s=1,sum=0;
        dfs(x[i],y[i]);
        s*=sum;sum=0;
        memset(dp,0,sizeof dp);
        dfs(y[i],x[i]);
        s*=sum;sum=0;
        ans=max(s,ans); 
    }
    cout<<ans;
    return 0;
}