https://vjudge.net/problem/CodeForces-132C
제목: F는 앞으로 간다는 뜻, T는 뒤로 돌아간다는 뜻으로 문자를 N번 수정할 기회가 있다. 최대 얼마나 멀리 갈 수 있느냐고 묻는다.
사고방식: dp[i][j][d]는 앞의 i자 문자가 j번을 수정하고 k의 길이를 갔음을 나타낸다. 현재 방향은 d의 상태의 최대 길이이다.
그래서 관계식을 점차적으로 미룰 수 있는데, i번 문자가 'F' or 'T' 일 때
그리고 다차원 추이 dp는 현재 i, j가 모두 오래된 i, j가 추론한 것이다. 즉, i-1, j-k는 사실 기억화 폭력이다.
주의:max를 사용하려면 먼저 모두 -inf로 초기화한 다음에 dp[0][0][1], dp[0][0]를 0으로 초기화해야 한다. 또한 j, k의 매거의 시작은 0에서 n, j까지임을 주의해야 한다.
#include
#include
#include <string >
#include
#include
#include
#include
#include
#include
#include <set >
#include
using namespace std;
const int maxn=110 ;
const int inf = 0x3f3f3f3f ;
char s[maxn];
int n;
int dp[110 ][55 ][2 ]; // i j (0 1 )
int main(){
scanf( " %s " ,s+1 );
scanf( " %d " ,&n);
int len = strlen(s+1 );
for (int i=0 ; i<=len; i++){
for (int j=0 ; j<=n; j++){
dp[i][j][ 1 ] = dp[i][j][0 ] = -inf;
}
}
dp[ 0 ][0 ][1 ]=dp[0 ][0 ][0 ]=0 ; // j、k
//
for (int i=1 ; i<=len; i++){
for (int j=0 ; j<=n; j++){ // j j-k ( i-1 )
for (int k=0 ; k<=j; k++){ //
if (s[i]==' T ' ){
if (k&1 ){ // dp， i、j
dp[i][j][0 ] = max(dp[i][j][0 ], dp[i-1 ][j-k][0 ]+1 );
dp[i][j][ 1 ] = max(dp[i][j][1 ], dp[i-1 ][j-k][1 ]-1 );
}
else {
dp[i][j][ 0 ] = max(dp[i][j][0 ], dp[i-1 ][j-k][1 ]);
dp[i][j][ 1 ] = max(dp[i][j][1 ], dp[i-1 ][j-k][0 ]);
}
}
else {
if (k&1 ){
dp[i][j][ 0 ] = max(dp[i][j][0 ], dp[i-1 ][j-k][1 ]);
dp[i][j][ 1 ] = max(dp[i][j][1 ], dp[i-1 ][j-k][0 ]);
}
else {
dp[i][j][ 0 ] = max(dp[i][j][0 ], dp[i-1 ][j-k][0 ]+1 );
dp[i][j][ 1 ] = max(dp[i][j][1 ], dp[i-1 ][j-k][1 ]-1 );
}
}
}
}
}
printf( " %d " , max(dp[len][n][0 ], dp[len][n][1 ]));
return 0 ;
}
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
