首页 > 代码库 > 【解题报告】[动态规划] - PID90 / 未出现的子串

【解题报告】[动态规划] - PID90 / 未出现的子串

2024-07-02 22:00:29   229人阅读

原题地址：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 }
View Code

 

 


联系
我们