학습 내용

이번 주에 구간 DP를 학습하면 구간 DP의 내용을 이해하기 쉽고 실현하기 어렵다. 다중 순환은 항상 머리가 어지럽고 방향을 바꾸기 때문에 실현할 때 데이터가 대표하는 의미에 항상 주의하고 이를 깊이 있게 분석해야 한다.
개술
구간 dp는 말 그대로 구간에서 dp로 대부분의 문제의 상태는 구간(dp[l][r]와 같은 형식)으로 구성된다. 바로 우리가 큰 구간을 작은 구간으로 바꾸어 처리한 다음에 작은 구간을 처리한 후에 다시 거슬러 올라가 큰 구간의 값을 구할 수 있다. 주요한 방법은 두 가지가 있는데 그것이 바로 기억화 검색과 추이다.
추이로 해답을 구할 때 관건은 추이가 for순환 안의 순서이고 dp의 관건: 상태 이동 방정식이다.

//mst(dp,0)    DP  
for(int i=1;i<=n;i++)
{
    dp[i][i]=   
}
for(int len=2;len<=n;len++)  //    
for(int i=1;i<=n;i++)        //    
{
    int j=i+len-1;           //    
    if(j>n) break;           //    
    for(int k=i;k

문제 해결

돌병합

N무더기의 돌들이 한 줄로 늘어서 있는데, 매 무더기의 돌들은 일정한 수량이 있다.이제 N으로 돌을 쌓아 한 무더기로 만들어야 한다.합병의 과정은 매번 서로 인접한 두 무더기의 돌을 한 무더기로 쌓을 수 있을 뿐, 합병할 때마다 걸리는 대가는 이 두 무더기의 합이고 N-1번의 합병을 거쳐 한 무더기가 된다.총 대가의 최소치를 구하다.
입력
여러 그룹의 테스트 데이터를 끝까지 입력하십시오.각 그룹의 테스트 데이터 첫 줄에는 n의 정수 n이 있는데 n의 돌무더기가 있음을 나타낸다.다음 줄에는 n(0출력
출력 총 대가의 최소치, 단독 줄을 차지
샘플 입력

3

1 2 3

7

13 7 8 16 21 4 18

샘플 출력

9

239

아이디어:
우리 dp[i][j]는 제i더미에서 제j더미까지의 돌을 합병하는 최소한의 대가를 나타낸다. 그러면 한 무더기마다 두 무더기로 나눌 수 있고 서로 다른 분할 방법을 하나하나 열거하면 최소한의 대가를 찾을 수 있다.
상태 이동 방정식은
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
그 중에서 w[i][j]는 두 부분을 합친 대가, 즉 제i더미에서 제j더미까지의 돌개수의 합을 나타낸다. 조회를 편리하게 하기 위해 우리는sum[i]로 제1더미에서 제i더미까지의 돌개수를 나타낼 수 있다. 그러면 w[i][j]=sum[j]-sum[i-1].

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
    int stone[200],n,dp[200][200],sum[200];
    while(~scanf("%d",&n))
	{ 
	    memset(dp,0,sizeof(dp));
        scanf("%d",&stone[0]);
		sum[0]=stone[0];
        for(int i=1;i=0;i--)
		{
            for(int j=i+1;j=0;i--)
		{
            for(int j=i+1;j

괄호 일치

We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence, if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if a and b are regular brackets sequences, then ab is a regular brackets sequence. no other sequence is a regular brackets sequence For instance, all of the following character sequences are regular brackets sequences: (), [], (()), ()[], ()[()]
Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.
Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
((())) ()()() ([]]) )[)( ([][][) end Sample Output
6 6 4 0 6 제목: 최대 괄호 일치
dp[i][j]를 문자열의 i부터 j까지 괄호의 최대 일치수로 정의
그러면 만약에 우리가 i에서 j까지의 최대 일치를 알게 된다면 i+1에서 j+1까지의 최대 일치는 쉽게 얻을 수 있지 않을까요?
그러면 만약에 i개와 j개가 일치하는 괄호라면 dp[i][j]=dp[i+1][j-1]+2;
그러면 우리는 작은 것부터 큰 것까지 모든 i와 j 사이의 괄호 수를 열거한 다음에 일치하는 것을 만족시키면 위식 dp를 사용하고 매번 dp[i][j]를 최대치로 업데이트하면 된다.
최대 값을 업데이트하는 방법은 i와 j의 중간 값을 매거한 다음에 dp[i][j]=max(dp[i][j], dp[i][f]+dp[f+1][j])를 업데이트하는 것이다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define LL long long
#define MAXN 202
#define INF 999999
using namespace std;
int dp[MAXN][MAXN];
int main()
{
    string s;
    while(cin>>s)
    {
        if(s=="end")  break;
        memset(dp,0,sizeof(dp));
        int i,j,k,f,len=s.size();
        for(i=1; i

구역 숫자

Description
The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.
The goal is to take cards in such order as to minimize the total number of scored points.
For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000
If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150. Input
The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces. Output
Output must contain a single integer - the minimal score. Sample Input
6 10 1 50 50 20 5 Sample Output
3650
제목의 뜻

      ，       ，        ，                  ，          ，

이 문제는 나를 오랫동안 갇혔는데, 문제는 처음부터 어려웠다. DP 그룹을 어떻게 설정하는지, 나는 방법을 검색하고 시도했다.
k가 표시한 수에 의해 결정된 하위 서열의 폭을 순서대로 늘리고 하위 서열을 이동한다. 즉, i의 값을 바꾸고 i+k 사이의 원소를 훑어보고 dp[i][i+k]와 먼저 a[i]와 a[j] 사이의 수를 선택하고 a[j]와 a[i+k] 사이의 수를 비교한 다음에 마지막으로 a[j]만 남는다. 이 과정에서 얻은 것은 dp[i][j]+dp[j][i][i+k]]+a[i]]와 [i]a[i]a*a][j]의 크기와 원래의 크기만 남는다.

1. 양쪽 구간 개방

예를 들어 dp[i][j]의 의미는'i 오른쪽에서 j 왼쪽으로 가져오기'이다. 그러면 분명히 답안을 dpij에 저장할 수 있다. 그러면 결과는 dp1n이고 코드는 다음과 같다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define LL long long
int dp[110][110];
int main()
{
    int i,j,k,len,a[110];
    int n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(len=2;len<=n;len++)
        for(i=1;i+len<=n;i++)
        {
            dp[i][i+len]=INF;
            for(j=i+1;j

2. 좌폐우개 구간

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define LL long long
int d[105][105],a[105];
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
          cin>>a[i];
        memset(d,0,sizeof(d));
        for(int len=2;len

두 번째 최종 답안은 dp2n에 저장되어 있고 순환 경계에서도 이전과 차이가 있다.이것 또한 우리가 실현 과정을 할 때 반드시 설치된 수조와 변수의 의미에 주의해야 한다는 것을 더욱 잘 일깨워 줄 수 있다.

생각을 깨닫다.

전반적으로 구간DP는 생각하지만 실현하기 어려운 방법이다. 이것은 사용 숙련도에 더 큰 요구를 가진다. 원래 느리게 하고 같은 시간에 하는 것이 더 적으며 점점 느릴 뿐이다. 그리고 자신에게 일깨워야 한다. 나중에 공부하는 과정에서 이 부분을 되돌아보는 것을 잊지 말고 명작 제목을 잘 보존하고 자주 되돌아보아야 한다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

static 간단한 설명

static 방법은 일반적으로 정적 방법이라고 부른다. 정적 방법은 어떠한 대상에 의존하지 않고 접근할 수 있기 때문에 정적 방법에 있어this는 없다. 왜냐하면 그 어떠한 대상에도 의존하지 않기 때문이다. 대상이 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

2020년 4월 마지막 주