目录

C. Hamiltonian Wall

题意：

dp思路：

代码：

E. Negatives and Positives

题意：

dp思路：

代码：

C. Hamiltonian Wall

Problem - 1766C - Codeforces

题意：

给一个2*m的字符数组，能不能一笔把所有的B连起来

input

6

3

WBB

BBW

1

B

B

5

BWBWB

BBBBB

2

BW

WB

5

BBBBW

BWBBB

6

BWBBWB

BBBBBB

output

YES
YES
NO
NO
NO
YES

dp思路：

dp[ 1/2 ] [ j ]表示 第1/2行第 j 列能否作为画笔的终点

初始化：如果第一列的字符是B，从这个点开始，同时它是第1列的终点

一列一列往后扫，如果是W，连不到当前点，如果是B，则由前一列状态转移来

如果当前列两行都是B，由于一笔连成，画笔停在另外一行，即两行的状态交换

代码：

#include<bits/stdc++.h>
#define endl '\\n'
#define forn(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;void solve(){int n;cin>>n;string s1,s2;cin>>s1>>s2;vector<vector<int> >dp(3,vector<int>(n));dp[1][0]=(s1[0]=='B');      //初始化dp[2][0]=(s2[0]=='B');for(int i=1;i<n;i++){if(s1[i]=='W')dp[1][i]=0;   //不连当前点if(s2[i]=='W')dp[2][i]=0;if(s1[i]=='B')dp[1][i]=dp[1][i-1];  //状态转移if(s2[i]=='B')dp[2][i]=dp[2][i-1];if(s1[i]=='B'&&s2[i]=='B')swap(dp[1][i],dp[2][i]);//画笔连住在这一列}cout<<((dp[1][n-1]||dp[2][n-1])?"YES":"NO")<<endl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

E. Negatives and Positives

Problem - E - Codeforces

题意：

给一个数组，每次可以把相邻两项变为负数，求若干次操作后的最大数组元素之和

input

5

3

-1 -1 -1

5

1 5 -5 0 2

3

1 2 3

6

-1 10 9 8 7 6

2

-1 -1

output

1
13
6
39
2

dp思路：

dp [ 1/2 ] [ i ] 表示第 i 个元素 操作/不操作 后的最大前缀和

状态转移方程，dp [ 1 ] [ i ]  = max ( dp [ 1 ] [ i -1 ] , dp [ 2 ] [ i - 1 ] ) + a[ i ] 

dp [ 2 ] [ i ] = max ( dp [ 1 ] [ i-1 ] - 2*a[ i-1 ] , dp [ 2 ] [ i-1 ] + 2*a[ i-1 ] ) - a[ i ]  

代码：

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;void solve(){int n;cin>>n;vector<ll>a(n+1);vector<vector<ll> >dp(3,vector<ll>(n+1));for(int i=1;i<=n;i++)cin>>a[i];if(n==1){cout<<a[1]<<endl;return;}dp[1][2]=a[1]+a[2];        //初始化dp[2][2]=-a[1]-a[2];for(int i=3;i<=n;i++){dp[1][i]=max(dp[1][i-1]+a[i],dp[2][i-1]+a[i]);      //不翻转直接加上dp[2][i]=max(dp[1][i-1]-2*a[i-1]-a[i],dp[2][i-1]-a[i]+2*a[i-1]);    //翻转的话前去前一个的二倍}cout<<max(dp[1][n],dp[2][n])<<endl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int T=1;cin>>T;while(T--){solve();}return 0;
}