Topcoder SRM548 div2
500pt: 두 개의 답안, 매개가 제시한 답안이 수조를 단조롭게 증가시킬 수 있는지 판정합니다.
코드:
class KingdomAndTrees
{
public:
bool Check(int t,vector<int> heights)
{
int i,j,n;
n=heights.size();
for (i=0;i<n;i++)
{
if (i==0) heights[0]=max(heights[0]-t,1);
else
{
if (heights[i]+t<=heights[i-1]) return false;
if (heights[i]-t<=heights[i-1])
{
heights[i]=heights[i-1]+1;
}
else
{
heights[i]-=t;
}
}
}
return true;
}
int minLevel(vector<int> heights)
{
int l,r,mid,i,j,n;
n=heights.size();
l=0;
r=INF;
while(l<=r)
{
mid=(l+r)/2;
if (Check(mid,heights)==true) r=mid-1;
else l=mid+1;
}
return l;
}
};
1000pt: 시합이 끝나기 전에 3min에 제출했는데 급하게 썼고 세부 사항을 잘못 써서 시합을 끊었어요.
p[i], i는 상태를 나타낸다. 즉, 원래 암호의 몇 개의 데이터를 사용한 다음에 앞의 몇 개의 암호가 원래 암호보다 큰 것을 유지하고 앞의 몇 개의 암호가 원래 암호와 같으며 원래 암호보다 작은 세 개의 수를 유지한다.
만약 상태 p가 i로 옮길 수 있다면
만약에 p의 앞자리가 원래 암호와 같다면 새로 추가된 그 수가 조건에 부합되고 새로 추가된 이 수가 원래 암호에 해당하는 위치의 수와 같다면 i의 원래 암호와 같은 값이 업데이트된다. 만약에 원래 암호에 해당하는 위치의 수보다 크면 i의 원래 암호보다 큰 값을 업데이트한다. 그렇지 않으면 i의 원래 암호보다 작은 값을 업데이트한다.
그렇지 않으면 p의 원래 암호보다 큰 값과 원래 암호보다 작은 값을 통해 i의 큰 값과 작은 값을 업데이트합니다.
코드
typedef struct
{
long long big;
long long equal;
long long small;
}DP;
class KingdomAndPassword
{
public:
DP dp[(1<<16)+5];
int count[(1<<16)+5];
long long ten[17];
long long newPassword(long long oldPassword, vector<int> restrictedDigits)
{
int i,j,n,t,tag,p;
int old[20];
long long pp;
pp=oldPassword;
n=0;
while(oldPassword)
{
old[n++]=oldPassword%10;
oldPassword/=10;
}
oldPassword=pp;
for (i=0;i<n/2;i++)
{
t=old[i];
old[i]=old[n-i-1];
old[n-i-1]=t;
}
ten[0]=1;
for (i=1;i<=n;i++)
{
ten[i]=ten[i-1]*10;
}
memset(count,0,sizeof(count));
for (i=0;i<(1<<n);i++)
{
for (j=0;j<n;j++)
{
if ((i & (1<<j))!=0) count[i]++;
}
}
dp[0].big=0;
dp[0].small=0;
dp[0].equal=0;
for (i=1;i<(1<<n);i++)
{
dp[i].small=0;
dp[i].big=INF;
for (j=0;j<n;j++)
{
if ((i & (1<<j))==0) continue;
tag=old[j];
if (restrictedDigits[count[i]-1]==tag) continue;
p=i & (~(1<<j));
if (tag==old[count[i]-1] && count[i]==1)
{
dp[i].equal=tag*ten[n-count[i]];
continue;
}
if (count[i]==1)
{
if (tag>old[count[i]-1]) dp[i].big=min(dp[i].big,tag*ten[n-count[i]]);
if (tag<old[count[i]-1]) dp[i].small=max(dp[i].small,tag*ten[n-count[i]]);
continue;
}
if (dp[p].equal!=0)
{
if (tag>old[count[i]-1]) dp[i].big=min(dp[i].big,dp[p].equal+tag*ten[n-count[i]]);
if (tag==old[count[i]-1]) dp[i].equal=dp[p].equal+tag*ten[n-count[i]];
if (tag<old[count[i]-1]) dp[i].small=max(dp[i].small,dp[p].equal+tag*ten[n-count[i]]);
}
else
{
if (dp[p].big!=INF) dp[i].big=min(dp[i].big,dp[p].big+tag*ten[n-count[i]]);
if (dp[p].small!=0) dp[i].small=max(dp[i].small,dp[p].small+tag*ten[n-count[i]]);
}
}
}
if (dp[(1<<n)-1].equal!=0) return dp[(1<<n)-1].equal;
if (dp[(1<<n)-1].small==0 && dp[(1<<n)-1].big==INF) return -1;
if (dp[(1<<n)-1].small!=0 && dp[(1<<n)-1].big!=INF)
{
return oldPassword-dp[(1<<n)-1].small<=dp[(1<<n)-1].big-oldPassword?dp[(1<<n)-1].small:dp[(1<<n)-1].big;
}
if (dp[(1<<n)-1].small!=0) return dp[(1<<n)-1].small;
return dp[(1<<n)-1].big;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.