TOJ 1541 알파코드 선형 DP(점진)
1292 단어 점차 미루다
우선 숫자에 0이 있을 수 있기 때문에 초기화할 때 두 개가 필요하다. dp[0]=dp[1]=1;
계속 고려할 때 현재 비트ch[i]가'0'이면 i-1비트와 두 자릿수(10, 또는 20)를 구성해야 한다. 문자가 0으로 암호화되지 않았기 때문이다.이때: dp[i] = dp[i-2];'0'이 아니라면 i, i-1 두 사람이 11-26 사이의 수를 구성할 수 있는지 고려해야 한다. 가능하다면 dp[i]=dp[i-1]+dp[i-2]
만약에 구성된 숫자가 26보다 크면 dp[i]=d[i-1], 즉 구성할 수 없다.만약에 구성된 숫자가 1-10 사이라면 i-1위가 0이라는 뜻이다. 이때 이 0은 반드시 i-2와 쌍이 되기 때문에 dp[i]는 여전히 dp[i-1]이다.지추 공식이 있으면 코드가 쉬워요. 주의하세요. 수조를 크게 만드는 게 좋아요. 제목 중에 약간 작아요. 500,,
코드:
#include <string.h>
#include<stdio.h>
long long dp[50000];
char ch[50000];
int main()
{
while(scanf("%s",ch+1))// 1
{
int len=strlen(ch+1);
if(len==1&&ch[1]=='0') break;
dp[0]=1;dp[1]=1;
for(int i=2;i<=len;i++)
{
int t=(ch[i-1]-'0')*10+(ch[i]-'0');
if(ch[i]=='0')dp[i]=dp[i-2];
else if(t<=26&&t>10) dp[i]=dp[i-1]+dp[i-2];
else dp[i]=dp[i-1];
}
printf("%lld
",dp[len]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
P1722 매트릭스 II & P1044 창고 문제풀이블로그 원제 링크 1 1 1 1 1 원제 링크 2, 2, 2. 먼저 P1722\text{P1722} P1722를 살펴보겠습니다. 제목 요약: 하나 있다× n 2\times n 2×n의 격자, 현재 너는 그것들의 모든...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
