9.11~9.16 훈련---중요!게이지
31531 단어 훈련집
앞말(~쓸데없는 말)
동적 기획이란 큰 문제를 작은 문제로 나누어 해결하고 모든 작은 문제를 해결하여 문제의 답안을 저장하는 것을 말한다. 다시 사용할 때 직접 호출하여 중복 계산을 하지 않아도 프로그램 시간을 크게 단축할 수 있다.이번 주에 dp전당(xie)당(jiao) 대문에 들어서자마자 특별히 할 줄 몰랐습니다. 대부분은 dp를 직접 쓰지 않았습니다. 주로 기억화 검색을 사용했습니다. 기본적으로 dp와 같습니다. 단지 dp는 순환 중에 쓰기가 어려웠지만 더 간결하고 시간의 복잡도 상수도 적습니다. 기억화 검색은 쓰기에 적합합니다. 저처럼 연습한 후에 저도 dp를 직접 쓰기 시작했습니다.다음은 이번 주에 물이 빠진 dp문제...
A - Greenhouse Effect
자칫 피를 토할 뻔한 a제...Emuskald is an avid horticulturist and owns the world's longest greenhouse - it is effectively infinite in length.
Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.
Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.
Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders. 임의의 위치를 이동해서 가장 적은 이동 횟수를 물어보면 첫 번째 숫자의 배열이 점차적으로 줄어들지 않고 두 번째 숫자는 사실 아무 소용이 없다는 뜻이다.직접 착안하여 한 시간 넘게 썼는데 dp방정식이 틀린 것을 발견했다. 나중에야 비로소 가장 긴 비체감자 서열을 찾아서 잠깐 쓰면 ok가 된다는 것을 발견했다. dp문제는 정말 사유해야 한다!!코드는 기억화 검색으로 썼는데...
#include1);
} else if(a[y]==x) {
dp[x][y]=f(x,y+1)+1;
} else {
dp[x][y]=max(f(x,y+1),f(a[y],y+1)+1);
}
return dp[x][y];
}
int main() {
double p;
int i;
memset(dp,-1,sizeof(dp));
cin>>n>>m;
for(i=1; i<=n; i++)
scanf("%d%lf",&a[i],&p);
for(i=1; i<=n-1; i++) {
int pp=0;
ans=max(ans,f(a[i],i+1)+1);
}
if(n==1) {
cout<<0;
return 0;
}
cout< B - Boredom
Alex doesn’t like boredom. That’s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.
Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let’s denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.
Alex is a perfectionist, so he decided to get as many points as possible. Help him. 비교적 간단하다. 바로 포인트 경기제에 1~n의 수가 있다.ak를 선택하면 값이ak+1이고ak-1은 모두 선택할 수 없다(삭제에 해당한다). 그러나 총점에ak를 더해서 최대 몇 점을 얻을 수 있는지 물어보는 것은 여전히 기억화 검색이다.
#include1);
} C-Flowers
We saw the little game Marmot made for Mole’s lunch. Now it’s Marmot’s dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.
But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.
Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (109 + 7). 초등학교 오수에서 계단을 걷는 것과 같이 한 번에 한 걸음 또는 k걸음, 방법을 구할 수 있다... 종점에 이르렀다고 상상할 수 있다. 지금은 k걸음이나 1걸음을 뒤로 물러설 수 있다.. 그리고 이 절차를 반복하면 매번 답안 기록을 중복산(예를 들어 한 번 k걸음을 물러난 후의 방법은 k걸음과 같다) 아니면 기억화 검색을 할 수 있다.
#include1;ret[i]=i;
}
dp[k]=2;ret[k]=k+1;
for(i=k;i<=100000;i++)
{sol(i);
}
for(i=1; i<=t; i++) {
int ans=0;
scanf("%d%d",&a,&b);
if(a==1)
ans=ret[b];
else
ans=ret[b]-ret[a-1];
ans%=mod;
printf("%d
",(ans+mod)%mod);
}
return 0;
} D-Mashmokh and ACM
Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn’t able to solve them. That’s why he asked you to help him with these tasks. One of these tasks is the following.
A sequence of l integers b1, b2, …, bl (1 ≤ b1 ≤ b2 ≤ … ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all i (1 ≤ i ≤ l - 1).
Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7). 약간 난이도가 있다. 바로 n과 k를 주고 1–n이라는 n개수를 써서 k개를 골라 하나의 서열을 구성하라는 것이다. 이 서열은 임의의 뒤에 있는 것을 만족시키면 앞의 것을 정제할 수 있다.이 서열의 개수를 구하시오.말 안 해도 아시겠지만 저는 기억검색을 했어요.
#includeE-Hard problem
Vasiliy is fond of solving different tasks. Today he found one he wasn’t able to solve himself, so he asks you to help.
Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).
To reverse the i-th string Vasiliy has to spent ci units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.
String A is lexicographically smaller than string B if it is shorter than B (|A|
For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically. 좀 하드하긴 한데.n개의 문자열과 그것을 뒤집는 데 필요한 대가를 주십시오. (주: 문자열의 순서를 바꿀 수 없습니다.) 모든 문자열을 사전 순서대로 배열하는 데 필요한 작은 대가를 주십시오. (존재하지 않으면 출력 -1)방법은 각 문자열을 읽고 반전된 문자열을 기록한 다음에 첫 번째부터 dp를 시작합니다. 각각 앞의 것과 비교하고 네 가지 상황에 대해 토론하면 됩니다.이번에 드디어 순환에 dp를 직접 쓰려고 시도합니다!!정말 깔끔해요.
#include
} F-George and Job
The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn’t have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.
Given a sequence of n integers p1, p2, …, pn. You are to choose k pairs of integers:
[l1, r1], [l2, r2], ..., [lk,\8201] [l2,\8201] (1\8201 ≤\8201 l1\8201 r1\8201 in such a way that the value of sum is max imal possible. Help George to cope with with the sk. Tak with the Pik. Pik. Pik는 서로 겹치지 않는 길이로 서로 겹치지 않는 길이(서로 겹치지 않는 길이로 서로 겹치지 않는 길이로 서로 겹치지 않는 길이(서로 겹치지 않는 길이가 서로 겹치지 않는 길이가 서로 겹치지 않는 길이(서로 겹치지 않는 길이를 제시하경계도 중첩할 수 없음)의 폐구간으로 각 구간 내의 값과 최대를 나타낸다.다시 기억화 검색으로 돌아왔는데, 사실 이 글자는 dp로 직접 쓰는 것이 매우 빠르다...
#include
return dp[x][y];
}
int main() {
int i;
memset(dp,-1,sizeof(dp));
//freopen("in.txt","r",stdin);
cin>>n>>m>>k;
for(i=0;icin >>a[i];
for(i=0;i<=n-m;i++)
{if(i==0)
{for(int j=0;j<=m-1;j++)
b[0]+=a[j];
}
else
b[i]=b[i-1]+a[i+m-1]-a[i-1];
//cout<
}
cout<0 ,k);
}H-The least round way
There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that
starts in the upper left cell of the matrix; each following cell is to the right or down from the current cell; the way ends in the bottom right cell. Moreover, if we multiply together all the numbers along the way, the result should be the least “round”. In other words, it should end in the least possible number of zeros. 어려운 문제를 계산하자면 n*n의 행렬이 있는데 왼쪽 상단에서 오른쪽 하단(아래로 또는 오른쪽으로만 가능), 곱셈 끝에 최소 몇 개의 0이 있다.출력 0의 개수와 경로입니다.처음에 나는 매 수에 5인수를 포함하는 개수만 논의했는데 물이 20여 개밖에 안 될 줄은 생각지도 못했다. (사실은 데이터가 너무 약하다. 그렇지 않으면 gg이다) 이어서 나는 2인수를 포함하는 개수 상황을 보충한 후에 5와 비교한 결과 gg가 되었다. 데이터 범위에 아버지가 있는 0이 있다는 것을 발견했다. 보충은 마침내 지나갔다.코드는 예전과 같이 기억화 검색을 한다
#include
return cnt;
}
int cnt_2(int a){
int cnt=0;
while(a%2==0&&a>=2)
{a/=2;
cnt++;
}
return cnt;
}
int main() {
int n,i,j,x,ret1,ret2,ret,aa,bb;
memset(dp,-1,sizeof(dp));
stack<char> ans;
//freopen("in.txt","r",stdin);
cin>>n;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
int p;
scanf("%d",&p);
if(p==0)
{flag=1;aa=i;bb=j;
}
m[i][j]=cnt_0(p);
m2[i][j]=cnt_2(p);
}
dp[1][1]=m[1][1];
find_road(n,n);
ret1=dp[n][n];
memset(dp,-1,sizeof(dp));
dp[1][1]=m2[1][1];
find_otroad(n,n);
ret2=dp[n][n];
ret=min(ret1,ret2);
//cout<
if(ret>1&&flag==1)
{cout<<1<for (i=1;i<=aa-1;i++)
cout<<"D";
for(i=1;i<=bb-1;i++)
cout<<"R";
for(i=aa;i<=n-1;i++)
cout<<"D";
for(i=bb;i<=n-1;i++)
cout<<"R";
return 0;
}
else if(ret==ret1)
for(i=n,j=n;;)
{if(i==1&&j==1)break;
ans.push(road[i][j]);
if(road[i][j]=='R')j--;
else i--;
}
else if(ret==ret2)
for(i=n,j=n;;)
{if(i==1&&j==1)break;
ans.push(road1[i][j]);
if(road1[i][j]=='R')j--;
else i--;
}
cout<for (i=1;i<=2*(n-1);i++)
{printf("%c",ans.top());
ans.pop();
}
}총결산
dp는 매우 중요합니다. 우선 글씨를 쓰는 방법입니다. 저는 직접 써 보려고 합니다. 최대한 기억화 검색을 적게 해야 합니다. 더 중요한 것은 사유입니다. 오 선생님은 dp 사유가 정말 철저하고 어떤 어려운 문제도 말하지 않는다고 말씀하셨습니다.
좋은 웹페이지 즐겨찾기
