1.1438 C. Engineer Artem（思維）

我當(dāng)時(shí)不會(huì)看的題解，很自閉，沒(méi)想到今天看dalao,他也沒(méi)想到，hhhhhh

題目鏈接：https://codeforces.com/contest/1438/problem/C

題目大意：給你一個(gè)數(shù)字矩陣，你可以選擇任意位置+1操作（最多加一次），讓你左右相鄰和上下相鄰的數(shù)字都不相同。

解題思路：

這題上下左右不可以相同，但是斜著的都是可以相同的。就可以把矩陣分成兩塊，只需要保證一塊為奇數(shù)，另一塊為偶數(shù)即可。就一定不會(huì)相同的。

這道題的題解太巧了呀！！！我什么時(shí)候能有這樣的好腦子

AC代碼

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e2+4;
int mp[maxn][maxn];

int main(){
	int t;
	cin>>t;
	int n,m;
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>mp[i][j];
				if((i+j)%2==0){
					if(mp[i][j]%2!=0){
						mp[i][j]++;
					}	
				}else{
					if(mp[i][j]%2==0){
						mp[i][j]++;
					}
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++)
				cout<<mp[i][j]<<' ';
			cout<<endl;
		}
	
	}	
	return 0;
}

2.1389 B. Array Walk

dalao眼中的簡(jiǎn)單dp

題目鏈接：https://codeforces.com/contest/1389/problem/B

題目大意：從第一個(gè)位置進(jìn)行移動(dòng)，每次可向左或者向右移動(dòng)，數(shù)組大小為n，移動(dòng)次數(shù)為k，最多向左移動(dòng)次數(shù)為z，讓你求移動(dòng)得到的最大的加和。

樣例解釋：

第一個(gè)只能向右移動(dòng)： 1+5+4+3+2=15

第二個(gè)能向左移動(dòng)一次： 1 +5+4+5+3=19

.....

所以可以使用dp操作,因?yàn)閦<=5所以最多一次操作有5個(gè)可能的位置。

dp[i][j] //i代表第幾次操作，j代表當(dāng)前在哪個(gè)位置 
    
dp[1][2]=a[1]+a[2]//經(jīng)過(guò)一次操作，不可能在1的位置

dp[2][3]=dp[1][2]+a[3]
dp[2][1]=dp[1][2]+a[1]

dp[3][4]=dp[2][3]+a[4]
dp[3][2]=dp[2][3]+a[2]

dp[4][5]=dp[3][4]+a[5]
dp[4][3]=dp[3][2]+a[3],dp[3][4]+a[3]
dp[4][1]=dp[3][2]+a[1]

dp[5][6]=dp[4][5]+a[6]
dp[5][4]=dp[4][3]+a[4],dp[4][5]+a[4]
dp[5][2]=dp[4][3]+a[2],dp[4][1]+a[2]

但是n是1e5的數(shù)據(jù)大小，不能開(kāi)這么大，可以開(kāi)到dp maxn 10,10代表的是左移的次數(shù)，一次左移，兩個(gè)位置，因?yàn)橹荒苁亲笠坪陀乙疲圆黹_(kāi)的是兩個(gè)位數(shù)。5次兩個(gè)位數(shù)，第i次操作就是i，i - 2，

i - 4 , i - 6,i - 8

#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int dp[maxn][10];//第二個(gè)是當(dāng)前向左移動(dòng)的次數(shù) 
int main(){
	int t,n,k,z;
	cin>>t;
	while(t--){
		cin>>n>>k>>z;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=k+1;i++){ 
			for(int j=0;j<=z;j++){
				if(j==0) dp[i][0]=dp[i-1][0]+a[i];
				else{//一個(gè)j代表兩個(gè)位置。 
					dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
					dp[i][j]+=a[i-j*2];
				}
			}
		} 
		int ans=0;
		for(int i=0;i<=z;i++){
			ans=max(ans,dp[k+1][i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}