[SCOI2003]\u5b57\u7b26\u4e32\u6298\u53e0 <\/p>\n
Time Limit:10000MS Memory Limit:165536K
Total Submit:21 Accepted:15
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n \u6298\u53e0\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a Input <\/strong><\/p>\n \u4ec5\u4e00\u884c\uff0c\u5373\u5b57\u7b26\u4e32S\uff0c\u957f\u5ea6\u4fdd\u8bc1\u4e0d\u8d85\u8fc7100\u3002 <\/p>\n Output <\/strong><\/p>\n \u4ec5\u4e00\u884c\uff0c\u5373\u6700\u77ed\u7684\u6298\u53e0\u957f\u5ea6\u3002 <\/p>\n Sample Input <\/strong><\/p>\n NEERCYESYESYESNEERCYESYESYES<\/p>\n Sample Output <\/strong><\/p>\n 14<\/p>\n Hint <\/strong><\/p>\n \u4e00\u4e2a\u6700\u77ed\u7684\u6298\u53e0\u4e3a\uff1a2(NEERC3(YES)) <\/p>\n Source #include<cstdio> [SCOI2003]\u5b57\u7b26\u4e32\u6298\u53e0 Time Limit:10000MS Memory Limit:165536KTotal Submit:21 Accepted:15 Case Time Limit:1000MS Description \u6298\u53e0\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a 1. \u4e00\u4e2a\u5b57\u7b26\u4e32\u53ef\u4ee5\u770b\u6210\u5b83\u81ea\u8eab\u7684\u6298\u53e0\u3002\u8bb0\u4f5cS S 2. X(S)\u662fX(X>1)\u4e2aS\u8fde\u63a5\u5728\u4e00\u8d77\u7684\u4e32\u7684\u6298\u53e0\u3002\u8bb0\u4f5cX(S) SSSS\u2026S(X\u4e2aS)\u3002 3. \u5982\u679cA A\u2019, BB\u2019\uff0c\u5219AB A\u2019B\u2019 \u4f8b\u5982\uff0c\u56e0\u4e3a3(A) = AAA, 2(B) = BB\uff0c\u6240\u4ee53(A)C2(B) AAACBB\uff0c\u800c2(3(A)C)2(B)AAACAAACBB \u7ed9\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6c42\u5b83\u7684\u6700\u77ed\u6298\u53e0\u3002\u4f8b\u5982AAAAAAAAAABABABCCD\u7684\u6700\u77ed\u6298\u53e0\u4e3a\uff1a9(A)3(AB)CCD\u3002 Input \u4ec5\u4e00\u884c\uff0c\u5373\u5b57\u7b26\u4e32S\uff0c\u957f\u5ea6\u4fdd\u8bc1\u4e0d\u8d85\u8fc7100\u3002 Output \u4ec5\u4e00\u884c\uff0c\u5373\u6700\u77ed\u7684\u6298\u53e0\u957f\u5ea6\u3002 Sample Input NEERCYESYESYESNEERCYESYESYES Sample Output 14 Hint \u4e00\u4e2a\u6700\u77ed\u7684\u6298\u53e0\u4e3a\uff1a2(NEERC3(YES)) Source\u6655\u3002\u3002SCOI\u8fd9\u79cd\u7c7b\u578b\u7684\u9898\u76ee\u600e\u4e48\u8fd9\u4e48\u591a\u56e7\u3002\u3002\u8fd9\u9053\u9898\u5dee\u4e0d\u591a\u5427\uff0c\u4e5f\u662fDp\uff0c\u6bd4\u538b\u7f29\u8fd8\u7b80\u5355\uff0c\u5c31\u4e0d\u8bf4\u4e86\u3002\u3002\u53e6\u5916<?=\u8fd9\u4e2a\u64cd\u4f5c\u7b26\u5f88NB\u3002\u3002Code\uff1a #include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/210"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=210"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/210\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
1. \u4e00\u4e2a\u5b57\u7b26\u4e32\u53ef\u4ee5\u770b\u6210\u5b83\u81ea\u8eab\u7684\u6298\u53e0\u3002\u8bb0\u4f5cS S
2. X(S)\u662fX(X>1)\u4e2aS\u8fde\u63a5\u5728\u4e00\u8d77\u7684\u4e32\u7684\u6298\u53e0\u3002\u8bb0\u4f5cX(S) SSSS\u2026S(X\u4e2aS)\u3002
3. \u5982\u679cA A\u2019, BB\u2019\uff0c\u5219AB A\u2019B\u2019
\u4f8b\u5982\uff0c\u56e0\u4e3a3(A) = AAA, 2(B) = BB\uff0c\u6240\u4ee53(A)C2(B) AAACBB\uff0c\u800c2(3(A)C)2(B)AAACAAACBB
\u7ed9\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6c42\u5b83\u7684\u6700\u77ed\u6298\u53e0\u3002\u4f8b\u5982AAAAAAAAAABABABCCD\u7684\u6700\u77ed\u6298\u53e0\u4e3a\uff1a9(A)3(AB)CCD\u3002 <\/p>\n
\u6655\u3002\u3002SCOI\u8fd9\u79cd\u7c7b\u578b\u7684\u9898\u76ee\u600e\u4e48\u8fd9\u4e48\u591a\u56e7\u3002\u3002\u8fd9\u9053\u9898\u5dee\u4e0d\u591a\u5427\uff0c\u4e5f\u662fDp\uff0c\u6bd4\u538b\u7f29\u8fd8\u7b80\u5355\uff0c\u5c31\u4e0d\u8bf4\u4e86\u3002\u3002
\u53e6\u5916<?=\u8fd9\u4e2a\u64cd\u4f5c\u7b26\u5f88NB\u3002\u3002
Code\uff1a
<\/strong><\/p>\n
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=120;
char M[maxl];
bool S[maxl][maxl]={0};
int Dp[maxl][maxl];
bool Match(int p,int Len,int s)
{
if(Len%s)return false;
rep(i,Len) if(M[p+i]!=M[p+i%s]) return false;
return true;
}
int Cost(int x)
{
if(x<10) return 1;
return 1+Cost(x\/10);
}
int dfs(int l,int r)
{
int&x=Dp[l][r];if(S[l][r]) return x;
S[l][r]=true;int Len=r-l+1;x=Len;if(Len==1) return x;
for(int k=l;k<r;k++)x<?=dfs(l,k)+dfs(k+1,r);
for(int k=1;k<Len;k++)if(Match(l,Len,k))x<?=dfs(l,l+k-1)+2+Cost(Len\/k);
return x;
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>M;
cout<<dfs(0,strlen(M)-1)<<endl;
}<\/p>\n","protected":false},"excerpt":{"rendered":"