Day2

T1

题目：

        有n个Boss，每个boss有困难和简单两种类型（1/0），你的朋友可以直接干掉0类型的boss，但是他干掉1类型的boss时需要花费一个跳过点。你可以直接解决两种boss.

        每一轮中，你和你的朋友可以击败一到两个 Boss（每一回合都必须击败至少一个 Boss，不能跳过）。每次都是你朋友先行动，然后轮到你，再轮到你朋友，如此交替。第一回合由你的朋友开始。

        你的任务是计算，为了让你和你的朋友按顺序击败所有 n 个 Boss，你的朋友最少需要用多少个跳过点。

思路

        进行dp。

        设dp[i][0/1][1/2]表示第i个boss被 你/朋友 在第一次/第二次击败时的最小花费

        初始化：

                dp[1][1][1]=a[1]

                dp[1][1][2]=INF

                dp[1][0][2]=INF

                dp[1][0][1]=INF

        状态转移：

            dp[i][0][1]=min(dp[i-1][1][1],dp[i-1][1][2])

            dp[i][0][2]=dp[i-1][0][1]

            dp[i][1][1]=min(dp[i-1][0][1],dp[i-1][0][2])+a[i]

            dp[i][1][2]=dp[i-1][1][1]

         答案：

            min(dp[n][0][1],dp[n][0][2],dp[n][1][1],dp[n][1][2])

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
int dp[200005][3][5];
int main(){
int T;
cin>>T;
while(T--){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[1][0][1]=a[1];
    dp[1][0][2]=1e9;
    dp[1][1][1]=1e9;
    dp[1][1][2]=1e9;
    for(int i=2;i<=n;i++){
        dp[i][0][1]=min(dp[i-1][1][1],dp[i-1][1][2])+a[i];
        dp[i][0][2]=dp[i-1][0][1]+a[i];
        dp[i][1][1]=min(dp[i-1][0][2],dp[i-1][0][1]);
        dp[i][1][2]=dp[i-1][1][1];
    } 
    cout<<min(min(dp[n][1][1],dp[n][1][2]),min(dp[n][0][1],dp[n][0][2]))<<"\n";
}
    return 0;
} 

复杂度：

    空间：O(n)

    时间：O(n)

T2

题目

     定义一个k-树，具有如下性质：

• 每个顶点恰好有 $k$ 个子节点；
• 每条边都有一个权值；
• 对于从某个顶点出发连向其各个子节点的 $k$ 条边，它们的权值分别为 $1,2,3,\ldots,k$。

        现在问：从 k-树的根出发，路径权值之和为 n，且路径上至少包含一条权值不少于 d 的边，这样的路径有多少条？

• 数据范围：$1 \leq n, k \leq 100$；$1 \leq d \leq k$

思路：

        进行dp.

        状态表示：dp[i][0/1]表示和为i的路径的条数.0表示没有大于或等于d的边，1表示有了。

        状态转移：这个有点像那个爬楼梯问题。

for(int i=1;i<=n;i++){
    for(int j=1;j<=min(i,k);j++){
        if(j>=d)
            dp[i][1]+=dp[i-j][0]+dp[i-j][1];
        dp[i][0]+=dp[i-j][0];
        dp[i][1]%=MOD;
        dp[i][0]%=MOD;
    }
}

         初始化：

dp[0][0]=1;

        答案：

         dp[n][1]

代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
long long dp[105][5];
int main(){
    int n,k,d;
    cin>>n>>k>>d;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=min(i,k);j++){
            if(j>=d)
                dp[i][1]+=dp[i-j][0]+dp[i-j][1];
            else{
                dp[i][1]+=dp[i-j][1];
                dp[i][0]+=dp[i-j][0];
            }
            dp[i][1]%=MOD;
            dp[i][0]%=MOD;
        }
    }
    cout<<dp[n][1];
    return 0;
}

T3

题目：

给定一颗有n个顶点的数，每个顶点有两个值：l,r.对每个顶点赋一个值a,满足l<=a<=r,整棵树的美观度定义为树上所有边(u,v)的|au-av|之和。要你求出最大的美观度。

思路：

每个顶点要么选取l要么选r,这样美观度才能达到最大。所以我们进行树形DP的时候就有两种情态。

设dp[v][0/1]为顶点v选取l/r时产生的子树的最大美观度

转移公式：(u,v)

            dp[u][0]+=
                max(dp[v][1]+abs(r[v]-l[u]),
                    dp[v][0]+abs(l[u]-l[v]));
            dp[u][1]+=
                max(dp[v][1]+abs(r[v]-r[u]),
                    dp[v][0]+abs(l[v]-r[u]));

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int l[100005],r[100005];
vector<int>G[100005];
long long dp[100005][3];
void dfs(int u,int fa){
    if(u!=1&&G[u].size()==1){
        return;
    }
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(v!=fa){
            dfs(v,u);
            dp[u][0]+=
                max(dp[v][1]+abs(r[v]-l[u]),
                    dp[v][0]+abs(l[u]-l[v]));
            dp[u][1]+=
                max(dp[v][1]+abs(r[v]-r[u]),
                    dp[v][0]+abs(l[v]-r[u]));
        }        
    }

}
int main(){
    freopen("parsatree.in","r",stdin);
    freopen("parsatree.out","w",stdout);
cin>>T;
while(T--){
    memset(dp,0,sizeof dp);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<max(dp[1][0],dp[1][1])<<"\n";
    for(int i=1;i<=n;i++)G[i].clear();
}

    return 0;
}

T4:

题目：

 暴力优化。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int f[5005];
long long s[5005];
long long ans;
int ans1,ans2,ans3;
long long dfs(int a,int b,int c){
    long long tmp=0;
    tmp+=s[a]-s[0];
    tmp-=s[b]-s[a];
    tmp+=s[c]-s[b];
    tmp-=s[n]-s[c];
    return tmp;
}
int main(){
    freopen("fs.in","r",stdin);
    freopen("fs.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>f[i];
        s[i]=s[i-1]+f[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=j;k<=n;k++){
                long long x=dfs(i,j,k);
                if(x>ans){
                    ans=x;
                    ans1=i;
                    ans2=j;
                    ans3=k;
                }
            }
        }
    }
    cout<<ans1<<" "<<ans2<<" "<<ans3;
    return 0;
}

T5

题目

给定n个整数，每个整数可以减去左右的数，然后这个整数减去删去的那个数，问最后剩下的整数的值最大为多少。整数中有负数。

思路：

1.全为正：sum-2*min

2.全为负：|sum|-2*min(这里的min是绝对值最小的min)

3.有正有负：sum,绝对值之和。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[500005];
int main(){
    freopen("slime.in","r",stdin);
    freopen("slime.out","w",stdout);
    cin>>n;
    bool flag1=1,flag2=1;
    long long sum=0;
    long long minn=1e9+10;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=abs(a[i]);
        minn=min(minn,abs(a[i]));
        if(a[i]>=0)flag1=0;
        if(a[i]<=0)flag2=0;
    }
    if(flag1||flag2){
        sum-=2*minn;
    }
    if(n==1){
        cout<<a[1];
        return 0;
    }
    cout<<sum;
	return 0;
}