带派大乱斗(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

，通通思路。

CPP

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);
}

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

CPP

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}

maxl 维护 $\max\limits_{0 \leq j \leq i}\{dp[j][0]\}$
minl 维护 $\max\limits_{0 \leq j \leq i}\{dp[j][1]\}$

CPP

#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$

CPP

#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$ 可以用仙法上跳一层或两层，不费时间，但要再爬过至少一层休息才可以继续使用仙术

\color{red}{wa}

的原因太多，考场思路不错，代码一坨

转移方程

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

#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]

CPP

#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分}}

正确转移

状态为

dp[i][j]

第

i

个数，高度为4j$是否能做到。

对于每个元素

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

CPP

#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

CPP

#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[i]$ 表示前 $i$ 个元素中 1 的个数
$i - sum[i]$ 表示前 $i$ 个元素中需要改变的 0 的个数
$sum[n] - sum[i]$ 表示后 $n-i$ 个元素中需要改变的 1 的个数

初始条件

sum[0] = 0

之所以

\color{red}{90}

分，因为没特判一开始就不用修改的情况。

CPP


#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}

分

代码

CPP

#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

CPP

#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}

分，因为数组又又开小了。

CPP

#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;
}

文章操作

T1

从 `i-1` 到 `i` 的转移：

T2

T3

转移方程

T4

T5

状态

初始条件

最终答案

T6

考场状态转移

正确转移

初始条件

T8

状态转移方程

初始条件

T9

转移方程

初始条件

T10

T11

状态转移方程

初始条件

T13

相关推荐

评论

带派大乱斗(1)

文章操作

T1

从 i-1 到 i 的转移：

T2

T3

转移方程

T4

T5

状态

初始条件

最终答案

T6

考场状态转移

正确转移

初始条件

T8

状态转移方程

初始条件

T9

转移方程

初始条件

T10

T11

状态转移方程

初始条件

T13

相关推荐

评论

从 `i-1` 到 `i` 的转移：