HDU 1505 City Game-dp-(최대 하위 매트릭스 모델)
1494 단어 DP
분석: 최대 매트릭스 공식으로 시간을 초과했습니다.사고방식을 바꾸면 이 문제는 1506과 관련이 있다. 먼저 각 층을 바탕으로 각 원소가 도달할 수 있는 가장 큰 높이를 계산한 다음에 1506과 같다.여기에서 높이를 구하는 것과 면적을 구하는 두 곳에서 dp 임시 저장 데이터를 사용했다.높이를 구하는 데는 이중 순환을 사용하고 각 층이 밑바닥으로 면적을 구하는 데는 이중 순환에 외층을 더하면 삼중 순환이다. 그러나 dp를 사용하여 중간 결과를 보존하기 때문에 이 삼중 순환은 시간을 초과하지 않는다.dp[j]는 현재 층의 j열이 도달할 수 있는 최대 높이를 나타낸다. 상태 이동: 1.a[i][j]='R'시 dp[j]=0;2. 그렇지 않으면 a[i-1][j]='F'가 되면 dp[j]++(이곳은 dp를 사용하고 앞층의 데이터를 저장하기 때문에 직접 +1하면 된다).a[i-1][j]='R'이면 dp[j]=1.층마다 면적을 구하는 알고리즘은 1506문제풀이
코드:
#include
using namespace std;
int t,m,n;
int mx,sum;
int l[1005],r[1005],dp[1005];
char a[1005][1005];
int max(int i,int j)
{
return i>j?i:j;
}
void fir()//
{
mx=0;
for(int j=0;j0&&dp[i]<=dp[t-1]) t=l[t-1];
l[i]=t;
}
for(int i=n-2;i>=0;i--){
int t=i;
while(t0&&dp[i]<=dp[t-1]) t=l[t-1];
l[i]=t;
}
for(int i=n-2;i>=0;i--){
int t=i;
while(t>t;
while(t--){
cin>>m>>n;
for(int i=0;i>a[i][j];
DP();
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
