$CF41D\ Pawn$

$problem$

与这题灰常的相似

然后内存可能过大开个滚动数组

因为数塔问题总是只需要上面一行的两个状态（这题就是数塔问题）

下面的代码与原题不符。（原题要输出路径）想抄的可以走了

输出路径只需要数组记录一下就好了。

#ifdef Dubug

#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long LL ;

inline LL In() {

	LL res(0),f(1);

	register char c ;

	while(isspace(c=getchar())) ;

	c == '-'? f = -1 , c = getchar() : 0 ;

	while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;

	return res * f ;

}

int n , m , k ;

const int N = 900 + 5 ;

const int Arr = 100 + 5 ;

short num[Arr][Arr] ;

bool dp[Arr][Arr][N] ;

bool b[N] ;

char s[Arr] ;

inline void get(int x) {

	for(register int i=1; i<=N/x; i++) b[i*x] = true ;

	return ;

}

inline void Ot() {

	memset(dp,0,sizeof(dp)) ;

	for(register int j=1; j<=m; j++) dp[n][j][num[n][j]] = true ;

	for(register int i=n-1; i>=1; i--)

		for(register int j=1; j<=m; j++)

			for(register int q=0; q<N; q++) {

				if(dp[(i+1)][j-1][q]) dp[i][j][q+num[i][j]] = true ;

				if(dp[(i+1)][j+1][q]) dp[i][j][q+num[i][j]] = true ;

			}

	int Max = -1 ;

	for(register int i=1; i<=m; i++)

		for(register int q=0; q<N; q++) if(dp[1][i][q] and b[q]) Max = max (Max,q) ;

	cout << Max << endl ;

}

signed main() {

#ifdef Online_Judge

	freopen("test.in","r",stdin) ;

	freopen("testdata.out","w",stdout) ;

#endif

	n = In() , m = In() , k = In() ;

	for(register int i=1; i<=n; i++) {

		scanf("%s",s+1);

		for(register int j=1; j<=m; j++) num[i][j] = s[j]&15 ;

	}

	get(k+1) ;

	return Ot() , 0 ;

}

#ifdef Dubug

#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long LL ;

inline LL In() {

    LL res(0),f(1);

    register char c ;

    while(isspace(c=getchar())) ;

    c == '-'? f = -1 , c = getchar() : 0 ;

    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;

    return res * f ;

}

int n , m , k ;

const int N = 900 + 5 ;

const int Arr = 100 + 5 ;

short num[Arr][Arr] ;

bool dp[2][Arr][N] ;

bool b[N] ;

char s[Arr] ;

inline void get(int x) {

    memset(b,false,sizeof(b)) ;

    for(register int i=1; i<=N/x; i++) b[i*x] = true ;

    return ;

}

inline void Ot() {

    memset(dp,0,sizeof(dp)) ;

    for(register int j=1; j<=m; j++) dp[n&1][j][num[n][j]] = true ;

    for(register int i=n-1; i>=1; i--)

        for(register int j=1; j<=m; j++)

            for(register int q=0; q<N; q++) {

                if(dp[(i+1)&1][j-1][q]) dp[i&1][j][q+num[i][j]] = true ;

                if(dp[(i+1)&1][j+1][q]) dp[i&1][j][q+num[i][j]] = true ;

            }

    int Max = -1 ;

    for(register int j=1; j<=m; j++)

        for(register int q=0; q<N; q++) if(dp[1][j][q] and b[q]) Max = max (Max,q) ;

    cout << Max << endl ;

}

signed main() {

#ifdef Online_Judge

    freopen("test.in","r",stdin) ;

    freopen("testdata.out","w",stdout) ;

#endif

    n = In() , m = In() , k = In() ;

    for(register int i=1; i<=n; i++) {

        scanf("%s",s+1);

        for(register int j=1; j<=m; j++) num[i][j] = s[j]&15 ;

    }

    get(k+1) ;

    return Ot() , 0 ;

}

巴特西

$CF41D\ Pawn$

最新文章

热门文章