带派大乱斗(1)

· · 个人记录

状态 补题 题目
\color{red}{60} \color{green}{100} 牛跳
\color{red}{30} \color{green}{100} 吃鱼
\color{red}{0} \color{green}{100} 再上锁妖塔
\color{green}{100} \color{green}{100} 守望者的逃离
\color{red}{74} \color{green}{100} fstring字符串
\color{red}{30} \color{green}{100} 桐桐的爬山计划
\color{grey}{无递交} 多米诺骨牌
\color{green}{100} \color{green}{100} DAY3拆分数字II
\color{red}{90} \color{green}{100} 晚餐队列安排
\color{red}{60} \color{green}{100} 变音量
\color{red}{90} \color{green}{100} 步步高升
\color{grey}{无递交} 花店橱窗布置
\color{red}{11} \color{green}{100} DAY1问题D

T1

删去背景，题目为：

有一个序列，请你选一个子序列，奇数位的数相加减去偶数位的和ans，输出最大的ans。

首先，我们可以先打个dfs，通通思路。

vector<int>a;
int dfs(int k){
    //cout<<k<<" ";
    if(k>p){
        int j=1,sum=0;
        for(int i:a){
            if(j)sum+=i,j=0;
            else sum-=i,j=1;
        }
        maxl=max(maxl,sum);
        return 0;
    }
    a.push_back(x[k]);
    dfs(k+1);
    a.pop_back();
    dfs(k+1);
}

经过思考，我们发现无法控制数字在第几位。 所以我们的状态定义为 

dp[i][j]//第i位数，j为1时代表这个数为加，j为0代表这个数为减

从 i-1 到 i 的转移：

\begin{aligned} dp[i][1] &= \max\limits_{0 \leq j < i}\{dp[j][0]\} + x[i] \\ dp[i][0] &= \max\limits_{0 \leq j < i}\{dp[j][1]\} - x[i] \end{aligned} 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p;
int ans=0;
int x[150005];
int  dp[150005][2];//带派[第几个][增加/减少] 
signed main(){
    cin>>p;
    for(int i=1;i<=p;i++)cin>>x[i];
    dp[0][0]=dp[0][1]=0;
    int maxl=0,minl=0;
    for(int i=1;i<=p;i++){
        dp[i][1]=maxl+x[i];
        dp[i][0]=minl-x[i];     
        maxl=max(maxl,dp[i][0]);
        minl=max(minl,dp[i][1]);    
        ans=max({ans,dp[i][0],dp[i][1]});//在转移时，有可能损失高度，题目说不一定全选，可以中断。
    }
    cout<<ans;
    return 0;
}

综上所述，从\color{green}{100}变了\color{red}{60}。

T2

吃粑粑

01背包模板题

数组开小了，从\color{green}{100}变了\color{red}{60 \times \frac{1}{2}}。

对于60%的数据，1 \le n \le 2000 对于100%的数据，1 \le n \le 30000,1 \le n \le 60000

#include<bits/stdc++.h>
using namespace std;
int t,m,w[30005],v[30005];//int t,m,w[2005],v[2005];
int dp[60005];//int dp[2005];
int main(){
    cin>>m>>t;
    for(int i=1;i<=m;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++)
        for(int j=t;j>=0;j--)
            if(j>=w[i])dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
            else dp[j]=dp[j];
    cout<<dp[t];
    return 0;
}

T3

去掉题目背景为

爬上第i层，花费h_i 可以用仙法上跳一层或两层，不费时间，但要再爬过至少一层休息才可以继续使用仙术

#### 转移方程 $$ dp[i][1] = \min(dp[i-1][0], dp[i-2][0]) $$ $$ dp[i][0] = \min(dp[i-1][1], dp[i-1][0]) + h[i] $$ ```cpp lines=17,18 #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; int n; int h[N]; int dp[N][2]; signed main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>h[i]; } //dp[0][0]=1e9; dp[1][0]=h[1]; dp[1][1]=0; for(int i=2;i<=n;i++){//改了i，忘了改初始化 dp[i][1]=min(dp[i-1][0],dp[i-2][0]);//dp[i][1]=min({dp[i-1][0],dp[i-2][0],dp[i][1]}); dp[i][0]=min(dp[i-1][1],dp[i-1][0])+h[i];//dp[i][0]=min({dp[i-1][1]+h[i],dp[i][0]}); } cout<<min(dp[n][1],dp[n][0]); return 0; } ``` ### T4 题目去掉背景为： >$m$: 初始魔法值 > >$s$: 需要到达的距离 > >$t$: 总时间 > >每秒可以选择：跑步前进 $17$ 米，或者使用魔法前进 $60$ 米（消耗 $10$ 点魔法） $sum1$: 表示纯跑步或混合策略能达到的最远距离 $sum2$: 表示优先使用魔法能达到的最远距离 ```cpp #include<bits/stdc++.h> using namespace std; int m,s,t,n=0; int sum1,sum2; int main(){ cin>>m>>s>>t; for(int i=1;i<=t;i++){ sum1+=17; if(m>=10)sum2+=60,m-=10; else m+=4; if(sum1<sum2)sum1=sum2; if(sum1>s){ cout<<"Yes"<<endl<<i<<endl; return 0; } } cout<<"No"<<endl<<sum1<<endl; return 0; } ``` ### T5 去题目背景题目为： >$n$ 字符串长度 > >有连续的$3$个由$A$，$B$，$C$各一个组成的子串,例如$ABC,ACB,BAC,BCA,CAB,CBA$,为$Fstring$。 注意到题目说 >一个只包含$A$，$B$，$C$三种字符的字符串 自然地想到，一个字符串只用判断连续三个字符是否不相同，就能说明是不是$Fstring$。 (考场实际打表，$\color{red}{74}$分) 所以只用记录长度为$i$,结尾两个字符即可 字符映射关系 $A = 1 \\B = 2\\C=3

状态

对于新加入的元素 kk：

ndp[j][kk] += dp[i][j] \quad \text{当满足条件：} \neg(i \neq j \land j \neq kk \land kk \neq i)

三个连续元素全部互不相同

初始条件

当 n = 2 时：

dp[i][j] = 1 \quad \text{对于所有 } i,j \in \{0,1,2\}

最终答案

\text{答案} = \sum_{i=0}^{2} \sum_{j=0}^{2} dp[i][j] 
#include<bits/stdc++.h>
using namespace std;
long long dp[3][3];
int main(){
    int n;
    cin>>n;
    if(n==1){
        cout<<3;
        return 0;
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            dp[i][j]=1;
    for(int k=3;k<=n;k++){
        long long ndp[3][3]={0};
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int kk=0;kk<3;kk++){
                    if(i!=j&&j!=kk&&kk!=i)continue;
                    ndp[j][kk]+=dp[i][j];
                }
            }
        }
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                dp[i][j]=ndp[i][j];
    }
    long long ans=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            ans+=dp[i][j];
    cout<<ans;
    return 0;
}

T6

去题目背景：

有n个数改变高度（初始为零），可上可下，高度不能为负

要求按顺序爬上爬下，最多需要多高的建筑物，要+2

考场状态转移

\left \{ \begin{array}{l} \text{加法:}dp[i][1] = \min(dp[i-1][1], dp[i-1][0]) + a[i]\\ \text{减法:}dp[i][0] = \begin{cases} \min(dp[i-1][1], dp[i-1][0]) - a[i] & \text{if } \min(dp[i-1][1], dp[i-1][0]) - a[i] \geq 0 \\ \infty & \text{otherwise} \end{cases}\\ \end{array} \right.

减法结果不能为负

上面转移有误，所以只有\color{red}{\text{30分}}

正确转移

状态为

对于每个元素 $a[i]$ 和当前差值 $j$： $$ \begin{aligned} \text{if } j + a[i] \leq h &: \quad dp[i][j + a[i]] = 1 \\ \text{if } j \geq a[i] &: \quad dp[i][j - a[i]] = 1 \end{aligned} $$ 其中转移条件为：$dp[i-1][j] = 1

初始条件

dp[0][0] = 1 
#include<bits/stdc++.h>
using namespace std;
int n,a[105];
bool dp[105][10005];
int main(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%2){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(int h=0;h<=sum;h++){
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=h;j++){
                if(!dp[i-1][j])continue;
                if(j+a[i]<=h)dp[i][j+a[i]]=1;
                if(j>=a[i])dp[i][j-a[i]]=1;
            }
        }
        if(dp[n][0]){
            cout<<h+2;
            return 0;
        }
    }
    cout<<"IMPOSSIBLE";
    return 0;
}

T8

题意

输出N有几种拆分方法

N = 1+1+1+1 ， 1+1+2 ，1+3 ，2+2 ，4

状态转移方程

dp[j] = dp[j] + dp[j - i]

其中 i 为当前考虑的数字，j 为目标和。

初始条件

dp[0] = 1 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int dp[55];
signed main(){
    memset(dp,0,sizeof dp);
    cin>>n;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            dp[j]+=dp[j-i];
        }
    }
    cout<<dp[n];
    return 0;
}

T9

去题目背景，题意为：

给一个长度为n的序列，仅有1和2。

请你修改序列，使序列前面为1,后面为2,尽可能少的修改数字，输出最小修改数。

十分容易想到状态

dp[i]

为前i个改为1,后i个改为2的最小修改数。

转移方程

dp[i] = (i - sum[i]) + (sum[n] - sum[i])

其中：

初始条件

sum[0] = 0

之所以\color{red}{90}分，因为没特判一开始就不用修改的情况。


#include<bits/stdc++.h>
using namespace std;
int n;
int d[30005];
int sum[30005]; 
int dp[30005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        if(d[i]==1)sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }

    // 添加特判
    bool ok = true;
    for(int i=2;i<=n;i++){
        if(d[i]==1&&d[i-1]==2){
            ok = false;
            break;
        }
    }
    if(ok){
        cout<<0;
        return 0;
    }

    for(int i=1;i<=n;i++){
        dp[i]+=i-sum[i];
        dp[i]+=sum[n]-sum[i];
    }
    int minl=0x3f3f;
    for(int i=1;i<=n;i++){
        minl=min(minl,dp[i]);
    }
    cout<<minl;
    return 0;
}

T10

思路参考,T6

考场代码为dfs,\color{red}{60}分

代码

#include<bits/stdc++.h>
using namespace std;
int n,st,mx;
int c[55];
bool dp[55][1005];
int main(){
    cin>>n>>st>>mx;
    for(int i=1;i<=n;i++)cin>>c[i];
    dp[0][st]=1;
    for(int i=1;i<=n;i++){
        bool ok=0;
        for(int j=0;j<=mx;j++){
            if(dp[i-1][j]){
                if(j+c[i]<=mx){
                    dp[i][j+c[i]]=1;
                    ok=1;
                }
                if(j>=c[i]){
                    dp[i][j-c[i]]=1;
                    ok=1;
                }
            }
        }
        if(!ok){
            cout<<-1;
            return 0;
        }
    }
    for(int i=mx;i>=0;i--){
        if(dp[n][i]){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

T11

去掉题目背景，题意为

已知初始值 W，每次可以减去 A 或 B，问正好减到Z的步数序列有多少种。

之所以\color{red}{90}分，因为数组又开小了。

状态转移方程

dp[i] = dp[i + a] + dp[i + b]

初始条件

dp[w] = 1 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10;//const int N=1e6+10;
int w,z,a,b,dp[N];
signed main(){
    cin>>w>>z>>a>>b;
    dp[w]=1;
    for(int i=w-1;i>=z;i--)dp[i]+=dp[i+a]+dp[i+b];
    cout<<dp[z];
    return 0;
}

T13

去掉题目背景，题意为

给你n个正整数，要求选一些数，使它们的和为S，输出任意一种方案。

背包问题。

之所以\color{red}{11}分，因为数组又又开小了。

#include<bits/stdc++.h>
using namespace std;
long long dp[10005];
int p[10005];  // 修改：使用一维数组记录路径
int w[10005];
int main(){
    int s,n;
    cin>>n>>s;
    for(int i=1;i<=n;i++)cin>>w[i];
    dp[0]=1;
    p[0]=0;  // 新增：初始化路径记录
    for(int i=1;i<=n;i++){
        for(int j=s;j>=w[i];j--){
            if(dp[j-w[i]] && !dp[j]){  // 修改：确保不覆盖已有方案
                dp[j]=1;
                p[j]=i;  // 修改：记录选择物品i达到重量j
            }
        }
    }
    if(!dp[s]){
        cout<<"-1";
        return 0;
    }
    deque<int> ans;
    int j=s;
    while(j>0){  // 修改：使用p数组回溯路径
        ans.push_front(w[p[j]]);
        j -= w[p[j]];
    }
    while(!ans.empty())cout<<ans.front()<<" ",ans.pop_front();
    return 0;
}