NOI 2.6 동적 계획 6045:식당 운영
2711 단어 NOI
6045:음식점 운영
총 시간 제한: 1000ms 메모리 제한: 65536kB
묘사 하 다.
북 대 정보 대학의 학우 샤 오 밍 은 졸업 후 창업 하여 식당 을 열 계획 이다.현재 모두 n 이 있다. 장 소 는 선택 할 수 있다.샤 오 밍 은 그 중에서 적당 한 위 치 를 선택 하여 식당 을 열 계획 이다.이. n 한 지점 이 같은 직선 위 에 배열 되 어 있다.우 리 는 정수 서열 m1,m2,...mn 을 사용한다. 그들의 상대 적 인 위 치 를 나타 낸다.지역 관계 로 식당 을 차 리 는 이윤 은 달라 질 것 이다.우리 에서 식당 을 차 리 는 이윤.자신의 식당 내부 경쟁 을 피하 기 위해 서 는 식당 간 의 거리 가 k 보다 커 야 한다.샤 오 밍 이 총 이윤 이 가장 큰 방안 을 선택 하도록 도와 주세요.
입력
표준 입력 은 여러 그룹의 테스트 데 이 터 를 포함한다.첫 줄 을 입력 하면 정수 T(1<=T<=1000)로 T 조 테스트 데이터 가 있 음 을 나타 낸다.이 어 T 조 의 연속 적 인 테스트 가 이 어 졌 다.각 조 의 테스트 데 이 터 는 3 줄,첫 번 째 줄:장소 총수 n(n<100),거리 제한 k(k>0&k<1000)이다.두 번 째 줄:n 개 장소의 위치 m1,m2,mn(1000000>mi>0 및 정수,오름차 순)세 번 째 줄:n 개 장소의 식당 이윤 p1,p2,...pn(1000>pi>0 및 정수)
출력
각 그룹의 테스트 데이터 에 대한 최대 이윤
샘플 입력
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30샘플 출력
40
30-----------------------------------------------------
문제 풀이 의 사고 방향.
동적 계획
dp[j]:a[i]를 선택 할 때 i~(n-1)의 최대 이윤
dp[j]=max(a[j]+dp[jj]),a[jj]는 모든 거리 a[j]가 k 를 초과 하 는 위치 입 니 다.
-----------------------------------------------------
코드
//
// dp[j]: a[i] i~(n-1)
// dp[j] = max(dp[j]+a[jj]), a[jj] a[j] k
#include
#include
using namespace std;
const int NMAX = 105;
int n,k;
int loc[NMAX] = {};
int pro[NMAX] = {};
int dp[NMAX] = {};
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin("0206_6045.txt");
int t,i,j,jj,mymax;
fin >> t;
for (i=0; i> n >> k;
for (j=0; j> loc[j];
}
for (j=0; j> pro[j];
}
if (n==1)
{
cout << pro[0] << endl;
continue;
}
dp[n-1] = pro[n-1];
for (j=n-2; j>=0; j--)
{
mymax = 0;
for (jj=j+1; jjk)
{
mymax = max(mymax,dp[jj]);
}
}
dp[j] = mymax + pro[j];
}
mymax = 0;
for (j=0; j> t;
for (i=0; i> n >> k;
for (j=0; j> loc[j];
}
for (j=0; j> pro[j];
}
if (n==1)
{
cout << pro[0] << endl;
continue;
}
dp[n-1] = pro[n-1];
for (j=n-2; j>=0; j--)
{
mymax = 0;
for (jj=j+1; jjk)
{
mymax = max(mymax,dp[jj]);
}
}
dp[j] = mymax + pro[j];
}
mymax = 0;
for (j=0; j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[NOI2011] 스마트카 경기(계산 기하학+동적 기획)[문제풀이] 경로는 직사각형 정점에서만 모퉁이를 돌 수 있기 때문에 4*n+2개의 점을 건설할 수 있다. 최단로를 구하려면 어떤 점이 직접 연결될 수 있는지 판단하기만 하면 된다. 직접 매거점 대 병합 도면, 복잡도...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
