PTA 엘리베이터 L3-020 - 3자 이상 삭제 (dp)
2144 단어 DP
사고방식: 과감하다dp[i][j]를 설정하여 이전 i자의 j자를 삭제한 결과입니다.한 문자를 삭제하는 것부터 생각해 보자. 현재 문자와 이전 문자가 같으면 중복되는 경우는 1가지밖에 없다. 바로 중복된 문자 중 하나를 삭제하는 것이다.만약 같지 않다면 이 문자를 삭제하거나 삭제하지 않는 것을 고려하면 결과는 i-1 문자의 삭제와 삭제하지 않는 상황의 합과 같다.두 문자를 삭제하는 것은 유사하다. 만약에 현재 문자가 이전 문자와 같다면 abcdeff는 중복된 부분은 (abcde) f로 구성되어 있다. 현재의 f에 대해 삭제하지 않으면 앞의 f는 반드시 삭제해야 현재의 f가 삭제된 상황과 중복될 수 있기 때문에 삭제할 기회를 앞의 f에게 주고 하나가 남으면 abcde를 준다. 그래서 중복된 방안 수는 dp[i-2]이다[1].현재 문자가 이전 문자와 같으면 abcdefe 같은 경우 현재 e에 대해 삭제하지 않으면 앞의 f와 e를 삭제하고 현재 e와 f를 삭제하는 상황이 중복되기 때문에 중복되는 경우는 하나뿐입니다.두 문자를 삭제하는 중복 상황은 왜 상기 두 가지, 예를 들어 abcedfe만 삭제해야 하는지, dfe나 df, 즉 세 문자만 중복을 구성할 수 있다.세 글자를 삭제하는 방법은 유사하지만 조금 더 고려할 뿐이다. 나는 여기에 밤을 열거하고 똑같이 밀면 된다. abcdeff, abcdefe, abcedfe.
#include
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn=1e6+5;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll dp[maxn][4];
int main()
{
std::ios::sync_with_stdio(false);
string s;
while(cin>>s)
{
memset(dp,0,sizeof(dp));
int l=s.length();
dp[1][1]=dp[1][0]=dp[3][3]=dp[2][2]=dp[2][0]=dp[3][0]=1;
for(int i=2; i<=l; i++)
{
dp[i][0]=dp[i-1][0];
if(s[i-1]==s[i-2])
{
dp[i][1]=dp[i-1][1]+dp[i-1][0]-1;
dp[i][2]=dp[i-1][2]+dp[i-1][1]-dp[i-2][1];
dp[i][3]=dp[i-1][3]+dp[i-1][2]-dp[i-2][2];
}
else if(i>=3&&s[i-1]==s[i-3])
{
dp[i][1]=dp[i-1][1]+dp[i-1][0];
dp[i][2]=dp[i-1][2]+dp[i-1][1]-dp[i-2][0];
dp[i][3]=dp[i-1][3]+dp[i-1][2]-dp[i-3][1];
}
else
{
dp[i][1]=dp[i-1][1]+dp[i-1][0];
dp[i][2]=dp[i-1][2]+dp[i-1][1];
dp[i][3]=dp[i-1][3]+dp[i-1][2];
if(i>=4&&s[i-1]==s[i-4])
dp[i][3]--;
}
}
// cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
