首页 > 代码库 > 【解题报告】[动态规划] - PID90 / 未出现的子串
【解题报告】[动态规划] - PID90 / 未出现的子串
原题地址:http://www.rqnoj.cn/problem/90
解题思路:题目看起来不太像动态规划。。。
我用一个数组f[i][j]来表示在数组第i个元素的后面第一次出现j的位置,为-1则是没出现过。
然后每次查找最大的位置即可。如题目例子中:
f 1 3 5 2 4 1 3 5 2 2 2 2 3 4 1 5 3 2
-----------------------------------------------------------
1 1 6 6 6 6 6 15 15 15 15 15 15 15 15 15 -1 -1 -1 -1
2 4 4 4 4 9 9 9 9 9 10 11 12 18 18 18 18 18 18 -1
3 2 2 7 7 7 7 7 13 13 13 13 13 13 17 17 17 17 -1 -1
4 5 5 5 5 5 14 14 14 14 14 14 14 14 14 -1 -1 -1 -1 -1
5 3 3 3 8 8 8 8 8 16 16 16 16 16 16 16 16 -1 -1 -1
从第0位置开始查找,找出f[0][1]~f[0][q]中的最大值。下一次就从这个最大值的地方开始查找,直到查找到f[0][1]~f[0][q]存在-1为止。
查找的次数就是答案。
代码:
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int s[100005]; 5 int f[100005][10]; 6 int n,q; 7 int main() 8 { 9 int i,j; 10 //freopen("out.txt","w",stdout); 11 scanf("%d%d",&n,&q); 12 for(i=1;i<=n;i++) 13 { 14 scanf("%d",&s[i]); 15 } 16 int fend[10]; 17 for(j=1;j<=q;j++) 18 { 19 fend[j]=-1; 20 } 21 for(i=n;i>=0;i--) 22 { 23 for(j=1;j<=q;j++) 24 { 25 f[i][j]=fend[j]; 26 } 27 fend[s[i]]=i; 28 }/* 29 for(j=1;j<=q;j++) 30 { 31 for(i=0;i<=n;i++) 32 { 33 printf("%3d",f[i][j]); 34 } 35 printf("\n"); 36 }*/ 37 int ans=1; 38 i=0; 39 int max; 40 while(1) 41 { 42 max=0; 43 for(j=1;j<=q;j++) 44 { 45 if(f[i][j]==-1) {max=-1;break;} 46 if(max<f[i][j]) max=f[i][j]; 47 } 48 if(max==-1) break; 49 else 50 { 51 i=max; 52 ans++; 53 //printf("i=%d\n",i); 54 } 55 } 56 printf("%d\n",ans); 57 return 0; 58 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。