poj 간단한 dp문제 몇 개
제목:poj1836
제목: 수열을 먼저 점차적으로 늘린 다음에 점차 줄이는 형식을 구하려면 빼야 할 숫자 개수를 구한다.물론 직접 체감하거나 체감하기만 하고 체감하지 않을 수도 있다.분석: 가장 긴 점증자 서열의 방법으로 구한 다음에 두 개의 기점의 위치를 일일이 열거하면 된다.
#includeint k=lower_bound(g+1,g+1+n,A[i])-g;
d[i]=k;
g[k]=A[i];
}
}
int d1[N],d2[N];
double a[N],b[N],g[N];
int n;
int main()
{
// freopen("f.txt","r",stdin);
scanf("%d",&n);
for(int i=0;iscanf("%lf",&a[i]),b[n-i-1]=a[i]; //b
LIS(n,d1,g,a);
LIS(n,d2,g,b);
int maxn=0;
for(int i=0;ifor(int j=0;j1;j++)maxn=max(maxn,d1[i]+d2[j]);
printf("%d
",n-maxn);
return 0;
}
제목:poj 1260
제목: 몇 종류의 진주와 그것들의 단가를 제시하고, 최소한의 돈으로 같은 수량의 같은 품질의 진주를 살 수 있도록 요구한다.[어떤 종류의 진주 n개(가격은 p)를 사더라도 (n+10)*p의 돈을 지불해야 한다. 즉, 10*p를 추가로 지불해야 한다. 분석: f[i]는 제i개 품목까지 최소 비용을 지불해야 한다는 뜻이다.그럼 f[i]=min {f[j]+(num[j+1]+num[j+2]+...+num[i])*p[i]}(j
#include
",f[n]);
}
return 0;
}
poj 1080
제목: LCS 변형 문제는 LCS의 사상에 따라 dp방정식을 추측하면 된다.
#include
",f[n1][n2]);
}
return 0;
}
poj 1159
제목: 문자열을 주고 최소한 몇 글자를 삽입하면 답장열을 구성할 수 있냐고요?분석: 정열과 역열의 가장 긴 공통 서열을 구하면 가장 일치하고 가장 적게 삽입된 것은 n-LCS이다.이 문제 n<=5000, int f[N][N]로 메모리를 초과할 수 있고 short로 바꿀 수도 있고 스크롤 그룹으로 바꿀 수도 있습니다.
#include
",n-f[k][n]);
return 0;
}
poj 2479
제목: 가장 큰 두 단락의 연속 서열과 정수 서열을 구합니다.분석:poj1836 문제와 유사하게 왼쪽에서 시작하는 최대 서열과 f[i], 오른쪽에서 시작하는 최대 서열과 d[i]를 구한다.그리고 중점을 일일이 열거하면 된다.f[i]는 왼쪽에서 i점까지의 가장 큰 연속 서열을 표시하고 d[i]는 오른쪽에서 i점까지의 가장 큰 연속 서열과
#include1]);
}
printf("%d
",ans);
}
return 0;
}
/*
3
10
1 -1 2 2 3 -3 4 -4 5 -5
2
1 -1
3
1 -1 2
*/ 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
poj 간단한 dp문제 몇 개제목:poj1836 제목: 수열을 먼저 점차적으로 늘린 다음에 점차 줄이는 형식을 구하려면 빼야 할 숫자 개수를 구한다.물론 직접 체감하거나 체감하기만 하고 체감하지 않을 수도 있다.분석: 가장 긴 점증자 서열의 방...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
