op拯救世界

用户名：dotcpp0718362

访问量：639

签　名：

等　　级
排　　名	17416
经　　验	774
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	南华大学
专　　业

　　自我简介：

TA的其他文章

3分钟写完一个题
浏览：133

直接使用动态规划解决，用dfs将超时
浏览：187

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

直接使用动态规划解决，用dfs将超时

　　作者: op拯救世界　　　　发表时间：2024-04-01 18:58:22 浏览：187　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-数组分割

此题可以使用dfs来骗分得大约20分。
以下是dp的方法

//如果sum的和不能为奇数，因为只有奇数加偶数才能为奇数。因此sum如果为奇数，直接输出0即可 
    // 以下分析都是基于sum为偶数进行的 
    //使用一个二维dp数组，dp[i][j]，表示进行到i时，选不选取这个数（0表示否，1表示YES）。
    //如果当前值为偶数：那么选取 与 不选取都为上一项的两倍（你不选，剩下的就会选，一样的）
    //如果当前值为奇数：方案数不变，因此是上一项的选与不选之和。 
    #include<iostream>
    #include<vector>
    using namespace std;
    #define ll long long
    const ll INF=1000000007;
    ll A[1005];  
    int main(){
    	int T,n;
        cin>>T;
        while(T--){
        	cin>>n;
        	vector<vector<ll> > dp(n+1,vector<ll>(2,0));
        	ll sum=0;
        	for(int i=1;i<=n;i++){
        	    cin>>A[i];
        	    sum+=A[i];
        	}
        	if(sum%2){
        		cout<<0<<endl;
        		continue;
    		} 
    		dp[0][0]=1;//什么都不选满足条件，dp[0][1]不存在,无需处理； 
        	for(int i=1;i<=n;i++){
        		if(A[i]%2){
        			dp[i][0]=2*dp[i-1][0]%INF;
    				dp[i][1]=2*dp[i-1][1]%INF; 
    			}
    			else{
    				dp[i][0]=(dp[i-1][0]+dp[i-1][1])%INF;
    				dp[i][1]=dp[i][0];
    			}
    		}
    		cout<<dp[n][0]%INF<<endl;
    	}
    	return 0;
    }# MarkDown编辑器基本使用说明

**如果这是您第一次使用MarkDown编辑器，建议先阅读这篇文章了解一下Markdown的基本使用方法。**

## 实时预览、全屏显示
简化后：空间复杂度极大的缩小，代码也更加简洁。
![](/image_editor_upload/20190606013233_25630.png)

**编辑器左边是输入框，右边是实际效果预览，可以点击编辑器上方界面小眼睛按钮来打开或关闭实时预览，如果感觉基本编辑界面太小太窄也可以使用全屏。**

## 插入代码
    #include<iostream>
    using namespace std;
    #define ll long long
    const ll mod=1000000007;
    int main(){
    	int T,n;
        cin>>T;
        while(T--){
        	cin>>n;
        	ll sum=0,t,x=1,y=0;
        	for(int i=1;i<=n;i++){
        	    cin>>t;
    			if(t%2) x=(x+y)%mod,y=x;
    			else x=(2*x)%mod,y=(2*y)%mod;
    			sum+=t;
    		}
        	if(sum%2)
        		cout<<0<<endl;
    		else
            	cout<<x<<endl;
    	}
    	return 0;
    }
**请不要在编辑框中直接粘贴代码，请使用代码块。**
- #### 代码块
![](/image_editor_upload/20190606022155_81717.png)
![](/image_editor_upload/20190606024121_61585.png)

**点击图标“代码块（多语言风格）”，即可在其中输入想要插入的代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606022918_54401.png)

**如上图代码块的开头与结尾都有三个间隔号（键盘左上角Esc下方按键），开头三个间隔号后的“c”即为代码语言。下面是一个例子：**

```c
	#include<stdio.h>
	int main()
	{
		int a,b;
		while(~scanf("%d%d", &a, &b))printf("%d\n",a+b);
		return 0;
	}
	```

- #### 行内代码
![](/image_editor_upload/20190606040412_74577.png)

**请点击“行内代码”按钮，再输入代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606040626_28452.png)

**如上图，与代码块不同，行内代码开头和结尾只有一个间隔号。下面是一个例子：**

`#include<stdio.h>`的作用是引入头文件！

## 标题样式

**标题支持6种样式，可点击H1~H6按钮变更标题样式；**

![](/image_editor_upload/20190606013846_99194.png)

**也可以直接输入“#”来编辑，“#”对应H1,“##”对应H2……**

*输入与预览图例：*
![](/image_editor_upload/20190606014119_69661.png)

## 文字样式

![](/image_editor_upload/20190606014703_35680.png)

**可点击按钮变更样式，或直接输入标记语法。**

*输入与预览图例：*
![](/image_editor_upload/20190606021227_16757.png)

**如上图中直接输入标记语法符号也可以达到想要的效果。下面是几个例子：**

*强调文本* _强调文本_
**加粗文本** __加粗文本__
　　==标记文本==
~~删除文本~~
> 引用文本

## 插入图片

![](/image_editor_upload/20190606023726_46319.png)

**点击“添加图片”按钮即可插入想要的图片，但上传有大小限制，图片如果过大请修改本地图片属性后再上传。**

## 插入表格

![](/image_editor_upload/20190606024844_48835.png)

**点击“添加表格”，填写一些基本属性，点击确定得到下图结果：**

![](/image_editor_upload/20190606025647_67742.png)

**在左边输入框中填入一些信息，即可完成表格：**

*输入与预览图例：*
![](/image_editor_upload/20190606025824_42776.png)

**你可以在左边输入框中任意增减图例中的竖线符号来调整表格格式。下面是一个例子：**

| 内容板块 | 大纲内容 | 学习目标 | …… |
| ------------ | ------------ |
| 标准语法 | 标准C语言全语法 | 熟练掌握C语言标准语法 |
| 实验与探究 | C语言特性  | 理解C语言底层原理 | 其他内容 |

## 列表

![](/image_editor_upload/20190606032543_63651.png)

**编辑一个列表，点击图标“无须列表”或“有序列表”，即可编辑内容，编辑好后按回车键，再次点击列表按钮开始编辑下一条。**

*输入与预览图例：*
![](/image_editor_upload/20190606033831_52890.png)

**你可以如上图中根据需求灵活使用其他标记语法与Tab键，改变文字样式与格式。下面是一个例子：**

- #### C语言快速入门

1. C语言第一个简单实例
	1. 实例说明

- **C语言的数据类型**

- 变量与常量数据
	- 数据类型和关键字
	- 本章总结与作业

## 科学公式 TeX(KaTeX)

**请在编辑器的预编辑内容中查看公式语法示例**

$$E=mc^2$$

行内的公式$$E=mc^2$$行内的公式。

$$x > y$$

$$$\sqrt{3x-1}+(1+x)^2$$$

$$\sin(\alpha)^{\theta}=\sum_{i=0}^{n}(x^i + \cos(f))$$

多行公式：

```math
\displaystyle
\left( \sum\_{k=1}^n a\_k b\_k \right)^2
\leq
\left( \sum\_{k=1}^n a\_k^2 \right)
\left( \sum\_{k=1}^n b\_k^2 \right)
```

```katex
\displaystyle
    \frac{1}{
        \Bigl(\sqrt{\phi \sqrt{5}}-\phi\Bigr) e^{
        \frac25 \pi}} = 1+\frac{e^{-2\pi}} {1+\frac{e^{-4\pi}} {
        1+\frac{e^{-6\pi}}
        {1+\frac{e^{-8\pi}}
         {1+\cdots} }
        }
    }
```

```latex
f(x) = \int_{-\infty}^\infty
    \hat f(\xi)\,e^{2 \pi i \xi x}
    \,d\xi
```

## 关于空格

**想要给一段文字添加多个　*空格符*　？**

**　　如果一定要输入多个连续空格符，可以切换输入法至全角输入（默认半角），然后再输入空格；**

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

### 来试试编辑一篇文章吧，祝您使用愉快！

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

op拯救世界

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

素数判断模板题(题解中的函数能用来判断大数是不是素数)

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

直接使用动态规划解决，用dfs将超时

评论区

精彩推荐

DNA （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

【出圈】（C语言代码）

不会做的

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

op拯救世界

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

素数判断模板题(题解中的函数能用来判断大数是不是素数)

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

直接使用动态规划解决，用dfs将超时

评论区

精彩推荐

DNA （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

【出圈】 （C语言代码）

不会做的

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

　　评论区

【出圈】（C语言代码）

C二级辅导-温度转换（C语言代码）