UVA 11552 Fewest Flops(시퀀스 DP, 레벨 4)
Crawling in process...
Crawling failed
Time Limit:2000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Submit
Status
Appoint description: System Crawler (2013-05-30)
Description
Problem F
FEWEST FLOPS
A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the character itself. For example, the string “aabbbaabaaaa” may be encoded as “2a3b2a1b4a”. (Note for this problem even a single character “b” is replaced by “1b”.)
Suppose we have a string S and a number k such that k divides the length of S. Let S1 be the substring of S from 1 to k, S2 be the substring of S from k + 1 to 2k, and so on. We wish to rearrange the characters of each block Si independently so that the concatenation of those permutations S’ has as few chunks of the same character as possible. Output the fewest number of chunks.
For example, let S be “uuvuwwuv” and k be 4. Then S1 is “uuvu” and has three chunks, but may be rearranged to “uuuv” which has two chunks. Similarly, S2 may be rearranged to “vuww”. Then S’, or S1S2, is “uuuvvuww” which is 4 chunks, indeed the minimum number of chunks.
Program Input
The input begins with a line containing t (1 ≤ t ≤ 100), the number of test cases. The following t lines contain an integer k and a string S made of no more than 1000 lowercase English alphabet letters. It is guaranteed that k will divide the length of S.
Program Output
For each test case, output a single line containing the minimum number of chunks after we rearrange S as described above.
INPUT 2 5 helloworld 7 thefewestflops
OUTPUT 8
10
Calgary Collegiate Programming Contest 2008
서열 구분
사고방식: 현재 블록이 몇 개, 마지막은 어느#include<iostream>
#include<cstring>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int mm=1e3+9;
const int oo=0x3f3f3f;
int dp[mm][27],has[mm][27],pos;
char s[mm];
int main()
{ int cas,K;
while(~scanf("%d",&cas))
{
while(cas--)
{ pos=0;
scanf("%d%s",&K,s);
int len=strlen(s);
clr(has,0);clr(dp,0x3f);
FOR(i,1,len)
{
if(i%K==1||K==1)++pos;
++has[pos][s[i-1]-'a'];
}
FOR(i,0,25)dp[0][i]=1;
int num;
FOR(i,1,pos)
{ FOR(j,0,25)
{int&ret=dp[i][j];
num=0;
if(has[i][j]==0)continue;
FOR(k,0,25)
if(has[i][k])++num;
FOR(k,0,25)
if(has[i][k]&&k!=j)
ret=min(ret,num-1+dp[i-1][k]);
else if(num==1&&k==j)ret=min(ret,dp[i-1][k]);
else ret=min(ret,num+dp[i-1][k]);
}
}
int ans=oo;
FOR(i,0,25)ans=min(ans,dp[pos][i]);
printf("%d
",ans);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
2 5 helloworld 7 thefewestflops
8
10
#include<iostream>
#include<cstring>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int mm=1e3+9;
const int oo=0x3f3f3f;
int dp[mm][27],has[mm][27],pos;
char s[mm];
int main()
{ int cas,K;
while(~scanf("%d",&cas))
{
while(cas--)
{ pos=0;
scanf("%d%s",&K,s);
int len=strlen(s);
clr(has,0);clr(dp,0x3f);
FOR(i,1,len)
{
if(i%K==1||K==1)++pos;
++has[pos][s[i-1]-'a'];
}
FOR(i,0,25)dp[0][i]=1;
int num;
FOR(i,1,pos)
{ FOR(j,0,25)
{int&ret=dp[i][j];
num=0;
if(has[i][j]==0)continue;
FOR(k,0,25)
if(has[i][k])++num;
FOR(k,0,25)
if(has[i][k]&&k!=j)
ret=min(ret,num-1+dp[i-1][k]);
else if(num==1&&k==j)ret=min(ret,dp[i-1][k]);
else ret=min(ret,num+dp[i-1][k]);
}
}
int ans=oo;
FOR(i,0,25)ans=min(ans,dp[pos][i]);
printf("%d
",ans);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.