转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
终于在TC过了两题,可惜第三题看错了题目。
250pt:只需要判断有几种颜色即可。
class ColorfulBricks{
public:
int countLayouts(string bricks){
bool flag[26];
int cnt=0;
memset(flag,false,sizeof(flag));
for(int i=0;i<bricks.size();i++)
if(!flag[bricks[i]-'A']){
flag[bricks[i]-'A']=true;
cnt++;
}
if(cnt==1)
return 1;
if(cnt==2)
return 2;
return 0;
}
};
500pt:枚举颜色,以及中心位置,然后往两边依次找目标颜色,先找最近的交换
class ColorfulChocolates{
public:
int maximumSpread(string chocolates, int maxSwaps){
int mmax=1;
int len=chocolates.size();
for(int i=0;i<26;i++){
for(int j=0;j<len-1;j++){
int a=j,b=j+1;
int tmp=0;
int step=maxSwaps;
bool flag[60];
memset(flag,true,sizeof(flag));
for(int x=a,y=b;x>=0||y<len;x--,y++){
if(x>=0&&x<len&&chocolates[x]==i+'A'){
if(step>=a-x){
tmp++;
step-=a-x;
a--;
}
}
if(y>=0&&y<len&&chocolates[y]==i+'A'){
if(step>=y-b){
tmp++;
step-=(y-b);
b++;
}
}
}
mmax=max(mmax,tmp);
}
}
return mmax;
}
};
1000pt:比赛的时候看成了26种颜色,以及是要用到多重集和矩阵的Polya计数,傻X了。只有3种颜色,DP可破。写了两个版本,第一个在本机测的没有问题,提交通不过,应该是内存大了。
注释部分:dp[pos][a][b][c][kind] ,表示前pos个位置,用了a个A,b个B,c个C。最后一位是kind的种数。枚举起点。
第二种:dp[fst][pre][a][b][c]表示第一个是fst,当前最后一个是pre,用了a个A,b个B,c个C的种数。记忆化搜索可破。
int dp[3][3][51][51][51];
int cnt[3],n;
class ColorfulCupcakesDivTwo{
public:
int slove(int pos,int pre,int fst,int a,int b,int c){
if(a<0||b<0||c<0)
return 0;
if(pos==n)
return pre!=fst;
if(dp[fst][pre][a][b][c]!=-1)
return dp[fst][pre][a][b][c];
int ret=0;
if(pos==0){
ret=(ret+slove(pos+1,0,0,a-1,b,c))%MOD;
ret=(ret+slove(pos+1,1,1,a,b-1,c))%MOD;
ret=(ret+slove(pos+1,2,2,a,b,c-1))%MOD;
}
else if(pre==0){
ret=(ret+slove(pos+1,fst,1,a,b-1,c))%MOD;
ret=(ret+slove(pos+1,fst,2,a,b,c-1))%MOD;
}
else if(pre==1){
ret=(ret+slove(pos+1,fst,0,a-1,b,c))%MOD;
ret=(ret+slove(pos+1,fst,2,a,b,c-1))%MOD;
}
else if(pre==2){
ret=(ret+slove(pos+1,fst,0,a-1,b,c))%MOD;
ret=(ret+slove(pos+1,fst,1,a,b-1,c))%MOD;
}
return dp[fst][pre][a][b][c]=ret;
}
int countArrangements(string cupcakes){
cnt[0]=cnt[1]=cnt[2]=0;
n=cupcakes.size();
for(int i=0;i<n;i++)
cnt[cupcakes[i]-'A']++;
memset(dp,-1,sizeof(dp));
return slove(0,0,0,cnt[0],cnt[1],cnt[2]);
}
};
/*
int dp[51][51][51][51][3];
int countArrangements(string cupcakes){
cnt[0]=cnt[1]=cnt[2]=0;
int n=cupcakes.size();
for(int i=0;i<n;i++)
cnt[cupcakes[i]-'A']++;
int ans=0;
for(int s=0;s<3;s++){
memset(dp,0,sizeof(dp));
if(s==0)
dp[1][1][0][0][0]=1;
else if(s==1)
dp[1][0][1][0][1]=1;
else
dp[1][0][0][1][2]=1;
for(int x=2;x<=n;x++){
for(int a=0;a<=cnt[0];a++)
for(int b=0;b<=cnt[1];b++)
for(int c=0;c<=cnt[2];c++)
if(a+b+c==x){
if(a){
dp[x][a][b][c][0]=(dp[x][a][b][c][0]+dp[x-1][a-1][b][c][1])%MOD;
dp[x][a][b][c][0]=(dp[x][a][b][c][0]+dp[x-1][a-1][b][c][2])%MOD;
}
if(b){
dp[x][a][b][c][1]=(dp[x][a][b][c][1]+dp[x-1][a][b-1][c][0])%MOD;
dp[x][a][b][c][1]=(dp[x][a][b][c][1]+dp[x-1][a][b-1][c][2])%MOD;
}
if(c){
dp[x][a][b][c][2]=(dp[x][a][b][c][2]+dp[x-1][a][b][c-1][1])%MOD;
dp[x][a][b][c][2]=(dp[x][a][b][c][2]+dp[x-1][a][b][c-1][0])%MOD;
}
}
}
ans+=(((-dp[n][cnt[0]][cnt[1]][cnt[2]][s]+dp[n][cnt[0]][cnt[1]][cnt[2]][0]+dp[n][cnt[0]][cnt[1]][cnt[2]][2]))+dp[n][cnt[0]][cnt[1]][cnt[2]][1])%MOD;
cout<<ans<<endl;
}
return ans;
}
*/
分享到:
相关推荐
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
SRM2Multi dumper for hsap
omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册pdf,omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册
SAP SRM 介绍
Driver HASP SRM emulator (x86)
多年SRM实施经验总结,对希望从事SRM实施或规划的同学们有帮助
srm后端JAVA 供应商平台管理 标准物资开票表 bus_standard_invoice_out增加freeze_quantity(冻结数量这一列)。 标准物资开票表 bus_standard_invoice_out的主键为{行项目、采购订单号、物料凭证}。 标准物资...
分块描述SRM系统的作用:寻源、协同和考核 涉及具体的业务用途,供前期规划作参考,可根据实际情况调整,再考虑如何实现
ASP SRM USB Command Line Dumper Instructions. HASP SRM USB命令行转储指令。 WARNING!!! Before make dump from dongle make sure that you install the ...2. 2. Execute h7dmp.exe file. 执行h7dmp.exe文件。
简叙什么是SRM,SRM解决什么问题,SRM有用途,SRM功能等
SRM210 (PA)SAP SRM Server Configuration (Col92) Configuration
HASP_SRM_Runtime_setup
SRM Overview中文版让你更直观更容易了解SRM是什么,能做什么
SRM空间富模型隐写分析算法,选区高维特征,使用集成分类器进行训练
SRM影像分割算法的matlab程序,主函数SRM_new
不仅可以阅读srm格式文件,还可以制作文档。完全绿色破解,是一款不错的srm阅读器。
Installation Guide for SAP SRM 7.0 EHP2 -
HASP SRM加密狗简介,阿拉丁公司的各种加密够简介
Workflow Guide SAP SRM 2007
不错的VMware SRM资料,可以看看