社区讨论
一放到这上面就都变为0了?
P1026[NOIP 2001 提高组] 统计单词个数参与者 8已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi6h105k
- 此快照首次捕获于
- 2025/11/20 04:44 4 个月前
- 此快照最后确认于
- 2025/11/20 04:44 4 个月前
为什么本地机上测试都是对的(下了数据),一放到这上面就都变为0了?
我没有用string啊?急急急!望大佬解答,谢谢。
CPP#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 250
using namespace std;
struct key{char s[2001],lon;}b[2001];
char a[5000];
int f[3000][3000];
int comp(key a,key b)
{
if(a.s[1]<b.s[1])return 1;
if(a.s[1]==b.s[1] && a.lon<b.lon)return 1;
if(a.s[1]>b.s[1])return 0;
if(a.s[1]==b.s[1] && a.lon>b.lon)return 0;
}
int delete1(int N,int sum)
{
int q,w,l1,l2,i,j,I,t;
for(q=1;q<=N;q++)
{
if(b[q].s[1]==b[q+1].s[1])
{
for(w=q+1;w<=N;w++)if(b[w+1].s[1]!=b[q].s[1])break; //找到相同的长度
l1=q;l2=w;q=w; //限定处理边界
for(i=l1;i<=l2;i++)
{
for(j=i+1;j<=l2;j++)
{
I=1;
if(b[j].lon=='|')continue;
for(t=1;t<=b[i].lon && t<=b[j].lon;t++)
{
if(b[i].s[t]!=b[j].s[t]){I=0;break;} //有差异,不为包含
}
if(I==1){b[j].s[1]='|';sum--;} //'|':127 //为包含关系(全部一样)删去长的(已经由长到短排序)
}
}
}
}
return sum;
}
int check(int ch,int mo,int n,int sum)
{
int q,w,I,e,r;
for(q=ch;q<=mo;q++) //枚举位置
{
for(w=1;w<=n;w++) //枚举第几个单词
{
if(a[q]==b[w].s[1])
{
I=1;
for(e=2,r=q+1;e<=b[w].lon;e++,r++) //比较
{
if(b[w].s[e]!=a[r]){I=0;break;}
if(r>mo){I=0;break;} //超出边界
}
if(I==1)sum++;
}
}
}
return sum;
}
int main()
{
//freopen("A.in","r",stdin);
int H,k,i,j,t,len,N;char ch;
scanf("%d%d\n",&H,&k);
for(i=1;i<=H;i++)
{
for(j=1;j<=20;j++)scanf("%c",&a[j+(i-1)*20]);//=getchar(); //拼接
scanf("\n");
}
len=H*20; //总长度
scanf("%d\n",&N);
for(i=1;i<=N;i++)
{
j=0;
while(666)
{
scanf("%c",&ch);//ch=getchar();
if(ch=='\n' || ch==' ' || ch=='\0' || ch<0)break; //读入单词
j++; b[i].s[j]=ch;
}
b[i].lon=j;
}
int R=N;
sort(b+1,b+N+1,comp); //第一次排序 (未删减)
N=delete1(N,N); //删除包含关系中较长的
sort(b+1,b+R+1,comp); //第二次排序(已删减) //此时N已经未实际长度
//DP:
for(i=1;i<=len;i++)f[i][1]=check(1,i,N,0); //预处理得只分一组的情况 //!!!!!!!!!!!!!!!!!!!!
for(i=2;i<=len;i++) //枚举长度 (i==2<------>j==2)
{
for(j=2;j<=min(i,k);j++) //从第二组分起
{
for(t=j-1;t<=i-1;t++) //分j-1组至少要有j-1个字母
{
f[i][j]=max(f[t][j-1]+check(t+1,i,N,0),f[i][j]);
}
}
}
printf("%d",f[len][k]);
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...