玄学DP0分求助
查看原帖
玄学DP0分求助
169422
vеctorwyx楼主2020/11/18 16:11

RT,跟std对拍一切正常,没拍出问题/kk。

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "algorithm"
#include "queue"
#include "cmath"
#include "vector"
#include "map"
#include "time.h"
#define data_of_qwq (gtdt(a[i][j + 1], i, j + 1) + gtdt(a[i + 1][j], i + 1, j))
#define data1 (gtdt(a[i][j + 1], i, j + 1))
#define data2 (gtdt(a[i + 1][j], i + 1, j))
#define data3 (gtdt(a[i][j - 1], i, j - 1))
#define data4 (gtdt(a[i - 1][j], i - 1, j))
using namespace std;
int h,w;
char a[1010][1010];
char gt(){
	char c = getchar();
	while((c < '0' || c > '9') && c !='.')
		c = getchar();
	return c;
}
int gtdt(char c,int x = 0,int y = 0){
	if(c == '.')
		return 0;
//	printf("%d-%d-%d ", c, x, y);
	return c - '0';
}
int dp[1010][1010][3][3];
char e[1010];
//三维: 0.无 ,1. 左下 , 2.右上
//四维: 0.无 ,1. 右 , 2.下 
signed main(){
	scanf("%lld%lld",&h,&w);/*
	for(int i = 1; i <= h ; i++)
		for(int j = 1; j <= w; j++)
			a[i][j] = gt();*/
	for(int i = 1; i <= h ; i++)
	{
		scanf("%s", e + 1);
		for(int j = 1;j <= w; j++)
			a[i][j] = e[j];
	}
			
	memset(dp,0x7f7f,sizeof(dp));
	dp[1][1][0][0] = (gtdt(a[1][1]) + gtdt(a[1 + 1][1]) + gtdt(a[1][1 + 1]));
	dp[1][1][0][1] = (gtdt(a[1][1]) + gtdt(a[1][1 + 1]));
	dp[1][1][0][2] = (gtdt(a[1][1]) + gtdt(a[1 + 1][1]));
	for(int i = 1; i <= h; i++)
		a[i][w + 1] = a[i][0] = '.';
	for(int i = 1; i <= w; i++)
		a[h + 1][i] = a[0][i] = '.';
/*	for(int i = 1; i <= h + 1 ; i++){
		for(int j = 1; j <= w + 1; j++)
			cout << a[i][j];
		cout <<"\n";
	}*/
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(i == 1 && j == 1)
				continue;
			if(i > 1){
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][2][2] + data_of_qwq);
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][1][2] + data_of_qwq);
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][0][2] + data_of_qwq);
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][0][2] + data1 + (data2 ? data3 : 0));
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][2][2] + data1 + (data2 ? data3 : 0));
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][1][2] + data1);
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][0][2] + data2 + (data1 ? data3 : 0));
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][2][2] + data2 + (data1 ? data3 : 0));
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][1][2] + data2);
				dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][0][0] + data_of_qwq);
				dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][1][0] + data_of_qwq);
				dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][2][0] + data_of_qwq);
				dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][0][0] + data1 + (data2 ? data3 : 0));
				dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][2][0] + data1 + (data2 ? data3 : 0));
				dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][1][0] + data1);
				dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][0][0] + data2 + (data1 ? data3 : 0));
				dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][2][0] + data2 + (data1 ? data3 : 0));
				dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][1][0] + data2);
			}
			if(j > 1){
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][2][1] + data_of_qwq);
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][1][1] + data_of_qwq);
				dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][0][1] + data_of_qwq);
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][0][1] + data1 + (data2 ? data4 : 0));
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][1][1] + data1 + (data2 ? data4 : 0));
				dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][2][1] + data1);
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][0][1] + data2 + (data1 ? data4 : 0));
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][1][1] + data2 + (data1 ? data4 : 0));
				dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][2][1] + data2);
				dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][0][0] + data_of_qwq);
				dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][1][0] + data_of_qwq);
				dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][2][0] + data_of_qwq);
				dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][0][0] + data1 + (data2 ? data4 : 0));
				dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][1][0] + data1 + (data2 ? data4 : 0));
				dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][2][0] + data1);
				dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][0][0] + data2 + (data1 ? data4 : 0));
				dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][1][0] + data2 + (data1 ? data4 : 0));
				dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][2][0] + data2);
			}
		}
	}
	cout << min(dp[h][w][0][0], min(dp[h][w][1][0], min(dp[h][w][2][0], min(dp[h][w][2][1], min(dp[h][w][1][1], min(dp[h][w][0][1], min(dp[h][w][2][2], min(dp[h][w][1][2], dp[h][w][0][2])))))))) << "\n";
	return 0; 
}
2020/11/18 16:11
加载中...