UVA 11552 Fewest Flops
2599 단어 dp
사고방식: dp[i][j]로 i단이 알파벳 j로 끝나는 가장 적은 블록의 개수를 대표한다.j 다음에 i단의 시작 자모 k를 매거하는 것을 확정하고 i-1단의 끝 자모와 다르면 dp[i][j]=min(dp[i-1][k]+cnt[i], dp[i][j]), 여기서 cnt[i]는 i단의 다른 자모의 개수를 나타낸다. 만약에 i-1단의 끝 자모와 같으면 dp[i][j]=min(dp[i-1][k]+cnt[i]-1, [dpi][j]])을 나타낸다.또한 i단의 시작 자모와 i-1단의 끝 자모가 다르면 dp[i-1][k]의 최소값은 확정할 수 있고 하나의 수조로 유지할 수 있으며 같은 상황이 있으면 하나만 줄이면 된다.
코드:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=1000+10;
char str[maxn];
int dp[maxn][26];
bool exits[maxn][26];
int cnt[maxn],minext[maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
int k;
scanf("%d",&k);
scanf("%s",str);
memset(dp,0xff,sizeof(dp));
memset(exits,0,sizeof(exits));
memset(cnt,0,sizeof(cnt));
int len=strlen(str);
int seg=len/k;
for(int i=0;i<len;i+=k)
for(int j=i;j<i+k;++j)
if(!exits[i/k+1][str[j]-'a'])
{
cnt[i/k+1]++;
exits[i/k+1][str[j]-'a']=true;
}
memset(exits[0],1,sizeof(exits[0]));
memset(dp[0],0,sizeof(dp[0]));
minext[0]=0;
for(int i=1;i<=seg;++i)
{
minext[i]=inf;
for(int j=0;j<26;++j)
if(exits[i][j])
for(int k=0;k<26;++k)
if(exits[i][k])
{
if(j==k&&cnt[i]!=1) continue;
if(dp[i][k]==-1)
dp[i][k]=minext[i-1]+cnt[i];
else
dp[i][k]=min(dp[i][k],minext[i-1]+cnt[i]);
if(dp[i-1][j]!=-1)
dp[i][k]=min(dp[i][k],dp[i-1][j]+cnt[i]-1);
minext[i]=min(minext[i],dp[i][k]);
}
}
printf("%d
",minext[seg]+1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.