8-3-COMPETITION
56622 단어 com
이번에는 동적 기획 중인 LCS, LIS, LCIS 특집...
A.Common Subsequence
바로: 두 개의 문자열을 주고 그 중 가장 긴 공통 서열의 길이를 구한다 ~ LCS
코드:
1 //memory:4276KB time:109ms
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<string>
6 using namespace std;
7
8 int c[1010][1010];
9
10 int maxx(int a,int b,int c)
11 {
12 if(b>a) a=b;
13 if(c>a) a=c;
14 return a;
15 }
16
17 int LCS_Lenght(string x,string y)
18 {
19 int m=x.length();
20 int n=y.length();
21 int i,j,v1,v2,v3;
22 memset(c,0,sizeof(c));
23 for(i=1;i<=m;i++)
24 for(j=1;j<=n;j++)
25 {
26 v3=c[i-1][j-1];
27 if(x[i-1]==y[j-1]) v3=v3+1;
28 v2=c[i-1][j];
29 v1=c[i][j-1];
30 c[i][j]=maxx(v1,v2,v3);
31 }
32 return c[m][n];
33 }
34
35 int main()
36 {
37 string x,y;
38 while(cin>>x>>y)
39 {
40 int p=LCS_Lenght(x,y);
41 cout<<p<<endl;
42 }
43 return 0;
44 }B.Palindrome
제목: 가장 긴 상승 서열을 구하는 문자열 ~ LIS
만약 표가 5001x5001의 메모리를 직접 사용한다면 (POJ에 있는 메모리는 매우 크고 코드는 통과할 수 있다) 최적화를 해야 한다.표의 각 단계는 표의 왼쪽, 위쪽, 왼쪽, 위쪽의 세 개의 점과 관계가 있고 각 줄의 점은 위 줄의 점과 관계가 있기 때문에 요구점의 값을 거슬러 올라갈 필요가 없을 때 2x5001의 표만 사용하면 된다~
코드:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<string>
6 using namespace std;
7
8 int c[2][5002],k;
9
10 int maxx(int a,int b,int c)
11 {
12 if(b>a) a=b;
13 if(c>a) a=c;
14 return a;
15 }
16
17 int LCS_Lenght(string x)
18 {
19 int i,j,v1,v2,v3;
20 memset(c,0,sizeof(c));
21 for(i=1;i<=k;i++)
22 for(j=1;j<=k;j++)
23 {
24 v3=c[(i-1)%2][j-1]; // ~ 25 if(x[i-1]==x[k-j]) v3=v3+1;
26 v2=c[(i-1)%2][j];
27 v1=c[i%2][j-1];
28 c[i%2][j]=maxx(v1,v2,v3);
29 }
30 return c[k%2][k];
31 }
32
33 int main()
34 {
35 string x;
36 while(cin>>k)
37 {
38 cin>>x;
39 int p=LCS_Lenght(x);
40 cout<<k-p<<endl;
41 }
42 return 0;
43 }//memory:344KB time:687ms
C.마법꼬치
두 문자열 a와 b를 주고 변환 관계를 보여 줍니다. 이 변환 관계를 통해 b가 a를 얻을 수 있는지, 삭제 문자를 통해 a를 얻을 수 있는지 확인하십시오.
코드:
//b의 문자가 변환 관계를 통해 a의 문자와 같은지 확인하기 위해 변환표를 작성합니다~
1 #include <stdio.h>
2 #include <string.h>
3 #include <iostream>
4 using namespace std;
5
6 const int N = 1005;
7
8 int main()
9 {
10 int cas,t;
11 scanf("%d",&t);
12 for(cas = 1; cas<=t; cas++)
13 {
14 getchar();
15 char s1[N],s2[N];
16 int len1,len2;
17 gets(s1);
18 gets(s2);
19 len1 = strlen(s1);
20 len2 = strlen(s2);
21 int n,i,j;
22 int change[30][30] = {0};
23 scanf("%d",&n);
24 for(i = 0; i<n; i++)
25 {
26 char a,b;
27 getchar();
28 scanf("%c %c",&a,&b);
29 change[a-'a'][b-'a'] = 1;//
30 }
31 j = 0;
32 int flag = 0;
33 for(i = 0; i<len1; i++)
34 {
35 if(j == len2)
36 break;
37 if(s1[i] == s2[j]) //
38 {
39 j++;
40 continue;
41 }
42 while(s2[j]!=s1[i])
43 {
44 if(j==len2)
45 {
46 flag = 1;
47 break;
48 }
49 if(change[s2[j]-'a'][s1[i]-'a'] == 1)
50 {
51 j++;
52 break;
53 }
54 else
55 j++;
56 }
57 }
58 printf("Case #%d: ",cas);
59 if(!flag)
60 printf("happy
");
61 else
62 printf("unhappy
");
63 }
64 return 0;
65 }//memory:232KB time:0ms
코드: http://blog.csdn.net/libin56842/article/details/8960511
방법2:
가장 긴 공통 서브시퀀스 (LCS) 를 찾으면 대응 관계에 약간의 변화가 있습니다 ~
코드:
1 #include<iostream>
2 #include<string>
3 #include<cstring>
4 using namespace std;
5 int dp[1005][1005];
6 bool has[128][128];
7 int maxi(int x,int y)
8 {
9 if(x>y)
10 return x;
11 else return y;
12 }
13 int main()
14 {
15 int i,j,t,m,count=0,len1,len2;
16 char a,b;
17 string str1,str2;
18 cin>>t;
19 while(t--)
20 {
21 count=count+1;
22
23 cin>>str1>>str2;
24 len1=str1.length();
25 len2=str2.length();
26 memset(dp,0,sizeof(dp));
27 memset(has,0,sizeof(has));
28 cin>>m;
29 for(j=1;j<=m;j++)
30 {
31 cin>>a>>b;
32 has[a][b]=1; // ~
33 }
34 cout<<"Case #"<<count<<": ";
35 for(i=1;i<=len1;i++)
36 for(j=1;j<=len2;j++)
37 {
38 if(str1[i-1]==str2[j-1]||has[str2[j-1]][str1[i-1]]==1) //has[][] ~
39 dp[i][j]=dp[i-1][j-1]+1;
40 else dp[i][j]=maxi(dp[i-1][j],dp[i][j-1]);
41 }
42
43 if(dp[len1][len2]==len1)
44 cout<<"happy"<<endl;
45 else cout<<"unhappy"<<endl;
46 }
47 return 0;
48 }//memory:4264KB time:78ms
D. 최소 차단 시스템
욕심 알고리즘:
이해하기 쉬운 해석을 찾아서 바로 붙였다.이 문제의 테스트 예에 대한 해석: 8개의 미사일이 순서대로 날아올 때 앞의 세 개의 미사일(300207155)에 대해 첫 번째 시스템으로 차단할 수 있다. 매번 기록을 갱신한다. 즉, 첫 번째 미사일에 대해 직접 차단하고 두 번째 미사일이 올 때도 첫 번째 시스템으로 차단한다. 기록은 207로 바뀐다. 첫 번째 시스템으로 세 번째 미사일을 차단한 후 기록은 155로 수정한다. 네 번째 미사일이 올 때 시스템 규정에 따라첫 번째 시스템은 네 번째 미사일에 대한 차단 임무를 실현할 수 없기 때문에 두 번째 시스템을 켜고 최소 시스템을 사용하기 위해서는 앞으로의 모든 미사일에 대한 욕심을 가져야 한다. 즉, 이 미사일과 이전의 미사일의 최소 기록을 순서대로 비교하고 이 미사일의 높이와 가장 가까운 기록을 찾아 이 미사일의 높이로 원래의 기록을 교체해야 한다. 마지막으로 수조의 개수는 가장 필요한 시스템 수이다.
코드:
#include<stdio.h>
#include<math.h>
int a[30001],b[30001];
int main()
{
int n,i,j,k;
while(scanf("%d",&n)!=EOF)
{
b[0]=0;k=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
for(j=0;j<=k;j++)
{
if(a[i]<b[j])
{
b[j]=a[i];
break;
}
else if(j==k)
{
k++;
b[k]=a[i];
break;
}
}
}
printf("%d
",k);
}
return 0;
}//memory:240KB time:15ms
동적 계획:
코드:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int t,a[1001],dp[1001],i,j,max;
while(scanf("%d",&t)!=EOF)
{
for(i=1;i<=t;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
max=-1;
for(i=1;i<=t;i++)
for(j=i-1;j>=0;j--)
if(a[i]>a[j] && dp[i]<dp[j]+1) // ~ 1~
dp[i]=dp[j]+1;
for(i=1;i<=t;i++)
if(max<dp[i]) max=dp[i];
printf("%d
",max);
}
return 0;
}//memory:232KB time:15ms
방법 3:
E문제에 대한 사고를 통해 D문제의 본질이 E문제와 같다는 것을 갑자기 발견했다. 마찬가지로 E문제의 방법으로 풀 수 있다. 그리고 학우들과의 토론을 거친다.음~최장 상승자 서열을 구하든 최장 하강자 서열을 구하든 모두 이 방법(약간 변형)을 사용할 수 있습니다~~~
코드:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 class Dolls
8 {
9 public:
10 int x,id;
11 }D[20000];
12
13 int main()
14 {
15 int n;
16 while(~scanf("%d",&n))
17 {
18 int i,minn;
19 memset(D,0,sizeof(D));
20 for(i=0;i<n;i++)
21 scanf("%d",&D[i].x);
22 int number=0,j;
23 for(i=0;i<n;i++)
24 if(D[i].id==0)
25 {
26 minn=D[i].x;
27 number++;
28 for(j=i+1;j<n;j++)
29 if(D[j].x<minn && D[j].id==0)
30 {
31 D[j].id=1;
32 minn=D[j].x;
33 }
34 }
35 printf("%d
",number);
36 }
37 return 0;
38 }E.Nested Dolls
제목: 러시아 인형들이 한 무더기 있는데, 이 인형들을 모두 묶어서 마지막에 얼마나 많은 인형이 남을지 보자~
방법1:
모든 아기를 x(너비)에 따라 큰 것부터 작은 것까지 순서를 정한다[주: 너비가 같을 때 y(높이)가 작은 것이 앞에 있다]. 그리고 첫 번째 아기부터 뒤에 있는 아기가 얼마나 들어갈 수 있는지, 넣을 수 있는 것은 모두 표시하고minn(아기를 넣을 수 있는 최대 높이)을 업데이트한다.다음 표시되지 않은 아이를 찾아서 반복해서...표시되지 않은 토시가 없을 때까지~ 조작도 적게 하고 토시만 몇 번 남았어요~
코드:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 class Dolls
8 {
9 public:
10 int x,y,id;
11 }D[20000];
12
13 bool comp(Dolls a,Dolls b) //
14 {
15 if(a.x==b.x) return a.y<b.y;
16 return a.x>b.x;
17 }
18
19 int main()
20 {
21 int t,n;
22 scanf("%d",&t);
23 while(t--)
24 {
25 int i,minn;
26 scanf("%d",&n);
27 memset(D,0,sizeof(D));
28 for(i=0;i<n;i++)
29 scanf("%d%d",&D[i].x,&D[i].y);
30 sort(D,D+n,comp);
31 int number=0,j;
32 for(i=0;i<n;i++)
33 if(D[i].id==0) // （ ）
34 {
35 minn=D[i].y;
36 number++;
37 for(j=i+1;j<n;j++)
38 if(D[j].y<minn && D[j].id==0) //
39 {
40 D[j].id=1; //
41 minn=D[j].y; //
42 }
43 }
44 printf("%d
",number);
45 }
46 return 0;
47 }//memory: 464KB time: 468ms
F.Greatest Common Increasing Subsequence
제목: 제목을 보면 알 수 있듯이 가장 긴 공공 상승자 서열을 구하는 것이다~~~~
//제목에 약간 구덩이가 있는 곳이 있는데 출력은 한 줄을 비워야 하고 마지막 출력은 비워서는 안 된다.안 그러면 PE...==
코드:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 int main()
7 {
8 long t,n,m,a[501],b[501],len[501],i,j,k,maxx;
9 scanf("%ld",&t);
10 while(t--)
11 {
12 scanf("%ld",&n);
13 for(i=1;i<=n;i++)
14 scanf("%d",&a[i]);
15 scanf("%ld",&m);
16 for(i=1;i<=m;i++)
17 scanf("%ld",&b[i]);
18 memset(len,0,sizeof(len));
19 for(i=1;i<=n;i++)
20 {
21 k=0;
22 for(j=1;j<=m;j++)
23 {
24 if(a[i]>b[j] && len[j]>len[k]) //len[j] b[j] ，
25 k=j; //len[k] a[i]>b[j] ， ~
26 if(a[i]==b[j])
27 len[j]=len[k]+1;
28 }
29 }
30 for(i=0,maxx=0;i<=m;i++)
31 if(len[i]>maxx) maxx=len[i]; // ~~
32 printf("%ld
",maxx);
33 if(t) printf("
");
34 }
35 return 0;
36 }//memory:228KB time:0ms
G. 지코 시리즈 - 완벽한 대형 I
F문제와 사실 비슷해요. 코드의 원리는 같지만 약간 바뀌었어요~
코드:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<string>
5 using namespace std;
6
7 int main()
8 {
9 int t,n,a[220],b[220];
10 scanf("%d",&t);
11 while(t--)
12 {
13 int mxx,number=0,i,j;
14 scanf("%d",&n);
15 memset(a,0,sizeof(a));
16 for(i=0;i<n;i++)
17 scanf("%d",&a[i]);
18 memset(b,0,sizeof(b));
19 for(i=n-1;i>=0;i--)
20 {
21 mxx=0;
22 for(j=0;j<=i;j++)
23 {
24 if(a[j]<a[i])
25 mxx=mxx>b[j]?mxx:b[j]; //mxx a[j]<a[i]
26 else
27 if(a[j]==a[i])
28 b[j]=mxx+1;
29 if(j<i && number<2*b[j]) number=2*b[j];
30 else
31 number=number>2*b[j]-1?number:2*b[j]-1;
32 }
33 }
34 printf("%d
",number);
35 }
36 return 0;
37 }//memory:228KB time:0ms
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
COM 스레드 모델COM은 Win32 스레드를 직접 사용하기 때문에 Win32 스레드에 대해 먼저 논의할 필요가 있습니다.Win32 시스템 스레드 자체는 하나이며, 응용 모델에 따라 작업 스레드와 UI 스레드 두 가지로 나눌 수 있습...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
