if (prlen <= opt[i]) {
tars = curs;
for (j = 1; j <= opt[i]; j++) {
nrt = i + j - 1;
tars |= (1 << nrt);
if (j == opt[i]) ans = min(ans, dfs(tars) + 1); } }
prlen = max(prlen - 1, opt[i]); } return mem[curs] = ans; }
int main () {
int kase, ka, k, i, j, res, ans; scanf(\
for (ka = 1; ka <= kase; ka++) {
scanf(\ slen = strlen(si); tlen = strlen(ti);
memset(mem, -1, sizeof(mem)); memset(called, 0, sizeof(called)); for (i = 0; i < tlen; i++) kmpinit(kmp[i], &ti[i]); for (i = 0; i < tlen; i++) {
res = 0;
for (j = 0, k = 0; j < slen; j++)
{
while (si[j] != ti[i + k] && k != -1) k = kmp[i][k]; k++;
res = max(res, k); }
for (j = slen - 1, k = 0; j >= 0; j--) {
while (si[j] != ti[i + k] && k != -1) k = kmp[i][k]; k++;
res = max(res, k); }
ttos[i] = res; }
ans = dfs(0);
if (ans >= mi) printf(\ else printf(\ }
return 0; }
河南省第三届ACM程序设计大赛答案
题数 类型 1 2 3 4 5 6 7 8 线段树；区间树 动态规划；枚举 图论 图论 动态规划 模拟 贪心；（树形）动态规划 线段树 【T1】提示：普通的做法时间复杂度为O(n) ，每次需要遍历区间内所有的数，但用线段树可以做到O(log n)。普通的做法是统计每天占用的房间总数，最大值即解。 【T2】提示：动态规划，求出X前的第一个素数以及其后的第一个素数，取其较近者。枚举（牺牲内存，换取时间），先离线求出范围内的所有素数（168个），存储起来，再找出离X最近且较大的那个素数即可。 【T3】提示：在给出图的基础上求出闭合环，边数与原始边数差值即解。 【T4】提示：求出由源点能到达的强连通分量，然后搜索求最优解。 【T5】提示：类似“TheTriangle”（http://acm.nyist.net/JudgeOnline/problem.php?pid=18），这个题利用数塔，数塔的思想就是从下往上来进行运算，不断的更新数组，最终求出最大和。有些细节要注意，当KK走倒最后一列是只能向下走，当KK走到最后一行时，只能向右走。 【T6】提示：先剔除无效竞价，再取最低竞价，为了保证先入为主，在求最小值的过程中应该使用条件min > p[i]而非min>= p[i]. 【T7】提示：贪心，求出每个商店（每一点）每买一磅食物需要的价钱，价钱中包括从这点运到终点需要的运费。 DP，转移方程（条件不同） DP[I][J]=MIN{DP[I-1][K]+K*K*(D[I]-D[I-1])+(J-K)*C[I]} J-F[I]<=K<=J 根据题目数据给的范围，500(I的范围)*10000(J的范围)*500(K的范围)肯定要超时。 于是用单调队列优化。 关于单调队列：队头的元素肯定是最小的（最大的） 取元素操作：从队头取出元素，直到该元素在要求的范围内（本题即为J-F[I]<=K<=J） 插入元素操作：若队尾元素比插入的元素要大，则删除。直到比待插入的元素小为止，然后再插入元素。
另外通过本题明确了队列的用法，头指针指向第一个元素，尾指针指向最后一个元素的后一位。若头尾指针相等则队列为空。
【T8】提示：线段树染色问题，和ZJU2301 Color the Ball类似，也是寻找最长连续区间。记录左右端点的连续情况。提示
河南省第四届ACM程序设计大赛答案
【T1】序号互换 #include
int i,sum=1;
for(i=1;i<=x;i++) sum*=n; return sum; }
int main() {
char **p,c;
int i,j,k,sum,n,l,*q; scanf(\
p=(char**)malloc(n*sizeof(char*)); for(i=0;i *(p+i)=(char*)malloc(Pow(10,4)*sizeof(char)); scanf(\ } for(i=0;i sum=0; l=0; while(*(*(p+i)+l)!='\\0') l++; if(*(*(p+i))>='A'&&*(*(p+i))<='Z') { for(j=0;j sum+=(*(*(p+i)+j)-'A'+1)*Pow(26,l-1-j); printf(\ } else { sum=0; j=0; while(*(*(p+i)+j)!='\\0') { sum+=(*(*(p+i)+j)-'0')*Pow(10,l-1-j); j++; } q=(int*)malloc(l*sizeof(int)); j=0; while(sum!=0) { q[j]=sum&; sum=sum/26; if(q[j]==0) {q[j]=26;sum--;} j++; } for(k=0;k printf(\ putchar('\\n'); } } free(p); system(\ return 0; } 【T2】节能 #include long digui(int now,long sum,int time); int i,v; long Wmin; scanf(\ scanf(\ P=(int **)malloc(N*sizeof(int *)); for(i=0;i *(P+i)=(int *)malloc(3*sizeof(int)); scanf(\ *(*(P+i)+2)=1; } Wmin=digui(v-1,0,0); printf(\return 0; } long digui(int now,long sum,int time) { int i; long w1=0,w2=0,sum1,sum2,time1,time2; P[now][2]=0; for(i=now-1;i>=0;i--) { if(P[i][2]==1) { time1=time+P[now][0]-P[i][0]; sum1=sum+time1*P[i][1]; w1=digui(i,sum1,time1); break; } } for(i=now+1;i if(P[i][2]==1) { time2=time+P[i][0]-P[now][0]; sum2=sum+time2*P[i][1]; w2=digui(i,sum2,time2); break; } } P[now][2]=1; if(w1==0&&w2==0) return sum; else if(w1!=0&&w2!=0) return w1 if(w1!=0) return w1;