hdu4352 (디지털 dp+상태 압축)
1402 단어 동적 계획 - 디지털 dp동적 기획
L과 R을 제시하여 [L, R]에서 가장 긴 증자 서열의 길이가 K와 같은 개수를 만족시키도록 한다.
문제 풀이:
장압은 생각지도 못했고 쿠엔빈의 것을 보고서야 알았다. 1<<10상압 저장수가 나타났는지.nlogn 점증 서열 알고리즘의 사상을 이용했다.
#include
#include
#include
#include
#include
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define mod 1000000007
#define maxn 30+5
lld dp[maxn][1<<10][15];
int bit[maxn];
lld L,R,K;
int NextSt(int st,int x)
{
// x ，nlogn
for(int i=x;i<10;i++)
if(st&(1<>=1;
}
return cnt;
}
lld dfs(int pos,int st,int zero,int f)
{
if(pos<1) return GetLen(st)==K;
if(!f&&dp[pos][st][K]!=-1) return dp[pos][st][K];
int last= f ? bit[pos] : 9;
lld res=0;
for(int i=0;i<=last;i++)
{
res+=dfs(pos-1,(zero==0&&i==0)?0:NextSt(st,i),zero||i,f&&(i==last));
}
if(!f) dp[pos][st][K]=res;
return res;
}
lld GetAns(lld n)
{
int len=0;
while(n)
{
bit[++len]=n%10;
n/=10;
}
return dfs(len,0,0,1);
}
int main()
{
int T;
memset(dp,-1,sizeof dp);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
cin>>L>>R>>K;
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제11회 산동성 대학생 프로그램 설계 경연대회 Adventurer's Guild(dp)전송문 제목: 몬스터의 수량 n, 캐릭터의 생명력 H, 캐릭터의 공격 S 건네기;다음 n행, 매 행위 매 몬스터의 혈액량 h, 공격 s, 가치 w; 매번 몬스터를 처치할 때마다 h의 혈액량과 s의 공격을 소모한다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
