몇 개의 기본 디지털 DP(hdu 2089,hdu 3555,uestc 1307 windy 수)
5087 단어 HDU
아주 기본 적 인 디지털 DP 를 몇 개 만 들 었 습 니 다.아주 물 입 니 다.약 폭 입 니 다.이제 진급 훈련 을 진행 해 야 합 니 다.
HDU 2089 싫어 62
http://blog.csdn.net/ACM_cxlove?viewmode=contents
4 가 나 오 거나 인접 한 62 가 나 오 면 안 된다.이 문 제 는 폭력 적 으로 시 계 를 쳐 서 해결 할 수 있다.
구체 적 으로 코드 에 설명 이 있어 요.
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int dp[10][3];
//dp[i][0],
//dp[i][1], , 2
//dp[i][2],
void Init(){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=6;i++){
dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; // 4 9 , 2 6
dp[i][1]=dp[i-1][0]; // 2
dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1]; // , 4, 2 4
}
}
int slove(int n){
int len=0,bit[10];
int tmp=n;
while(n){
bit[++len]=n%10;
n/=10;
}
bit[len+1]=0;
int ans=0;
bool flag=false;
for(int i=len;i;i--){
ans+=dp[i-1][2]*bit[i];
if(flag) // 4 62,
ans+=dp[i-1][0]*bit[i];
if(!flag&&bit[i]>4) // 4
ans+=dp[i-1][0];
if(!flag&&bit[i+1]==6&&bit[i]>2) // 6, 2, debug
ans+=dp[i][1];
if(!flag&&bit[i]>6) // 6, 2
ans+=dp[i-1][1];
if(bit[i]==4||(bit[i+1]==6&&bit[i]==2)) // 4 62
flag=true;
}
return tmp-ans;
}
int main(){
int l,r;
Init();
while(scanf("%d%d",&l,&r)!=EOF&&l+r)
printf("%d
",slove(r+1)-slove(l));
return 0;
}
HDU 3555 BOMB
http://acm.hdu.edu.cn/showproblem.php?pid=2089
인접 한 49 가 나 오 면 안 돼 요.
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
LL dp[21][3],n;
int len,bit[21];
//dp[i][0] i, 49
//dp[i][1] i, 49 9
//dp[i][2] i, 49
void Init(){
memset(dp,0,sizeof(dp));
dp[0][2]=1;
for(int i=1;i<20;i++){
dp[i][0]=(LL)dp[i-1][0]*10+dp[i-1][1];
dp[i][1]=dp[i-1][2];
dp[i][2]=(LL)dp[i-1][2]*10-dp[i-1][1];
}
}
int main(){
Init();
int t;
scanf("%d",&t);
while(t--){
scanf("%I64d",&n);
len=0;
n++;
while(n){
bit[++len]=n%10;
n/=10;
}
bit[len+1]=0;
LL ans=0;
bool flag=false;
for(int i=len;i;i--){
ans+=(LL)dp[i-1][0]*bit[i];
if(flag)
ans+=(LL)dp[i-1][2]*bit[i];
if(!flag&&bit[i]>4)
ans+=dp[i-1][1];
if(bit[i]==9&&bit[i+1]==4)
flag=true;
}
printf("%I64d
",ans);
}
return 0;
}
UESTC 1307 WINDY 수
http://acm.hdu.edu.cn/showproblem.php?pid=3555
인접 을 요구 하 는 수의 차 이 는 2 보다 크다.
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int dp[15][10];
//dp[i][j] i , j windy
void Init(){
memset(dp,0,sizeof(dp));
for(int i=0;i<=9;i++)
dp[1][i]=1;
for(int i=2;i<=10;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++)
if(abs(j-k)>=2)
dp[i][j]+=dp[i-1][k];
}
}
}
int slove(int n){
int len=0,bit[15];
while(n){
bit[++len]=n%10;
n/=10;
}
bit[len+1]=0;
int ans=0;
// 1 len-1
for(int i=1;i<len;i++)
for(int j=1;j<10;j++)
ans+=dp[i][j];
//
for(int j=1;j<bit[len];j++)
ans+=dp[len][j];
for(int i=len-1;i;i--){
for(int j=0;j<bit[i];j++)
if(abs(j-bit[i+1])>=2)
ans+=dp[i][j];
// ,
if(abs(bit[i]-bit[i+1])<2)
break;
}
return ans;
}
int main(){
Init();
int l,r;
while(scanf("%d%d",&l,&r)!=EOF)
printf("%d
",slove(r+1)-slove(l));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.