SSL·디지털 게임【DP】

11016 단어 DP

디지털 게임[DP] SSL 1653

Description--

Input--

Output--

Sample Input--

Sample Output--

문제풀이 사고방식--

코드 --

Description–

작은 W는 게임을 발명했다. 그는 칠판에 한 줄의 숫자 a1, a2, a3,......, an을 썼다. 그리고 너에게 M라운드의 기회를 주었다. 매번 매번 매번 그 중에서 한 줄의 숫자를 선택해서 지울 수 있다. 이어서 남은 모든 숫자ai는 한 개의 값을 점차 줄여야 한다.이렇게 m라운드를 반복하면 네가 지운 모든 숫자의 합이 네가 얻은 점수다.샤오W와 그의 친한 친구인 샤오Y가 이 게임을 했지만 그는 모든 a와 b 서열에 대해 샤오Y의 득점이 항상 그보다 높다는 것을 발견했기 때문에 그는 매우 불복했다.그래서 그는 네가 그를 도와 a와 b 서열에 대해 얻을 수 있는 최대 점수가 얼마인지 계산해 보라고 했다.

Input–

입력 파일의 첫 줄은 정수 n(1<=n<=2000)으로 숫자 개수를 나타낸다.두 번째 줄에 하나의 정수 m(1<=m<=n)는 라운드 수를 나타내고 다음 줄에 n개는 10000을 넘지 않는 정수, a1, a2, a3,......, an은 원시 서열을 나타내고 마지막 줄에 n개는 500을 넘지 않는 정수, b1, b2, b3,......,bn은 라운드마다 숫자마다 체감하는 값을 나타낸다.

Output–

출력 파일은 정수가 하나밖에 없어서 가장 큰 득점을 나타낸다

Sample Input–

3 3 10 20 30 4 5 6

Sample Output–

문제풀이 사고 –

우선, 만약 a[i].d가 a[j]에 있다.d 이전에 삭제하고 a[i].a[j]보다 작습니다.b면 우리는 이 두 수의 삭제 순서를 바꾸어 총계를 더욱 크게 할 수 있다.
그리고 F[i, j]를 설정하면 이전 i 개수에서 j 개수의 최대 점수를 삭제합니다.획득가능-상태 전이 방정식: F[i, j]=max(F[i-1, j], F[i-1, j-1]+a[i]-b[i]*(j-1))
요약:

b[i]를 큰 것부터 작은 것까지 정렬

이전 i개수에서 j개수를 삭제한 최대 점수 구하기

코드 –

#include
#include
#include
using namespace std;
int n,m,t,f[2000][2000];
int max(int x,int y)
{
	if (x>y) return x;
	return y;
}
struct hh
{
    int d,b;
}a[2000];
int cmp(hh x,hh y)
{
    if(x.b != y.b) return x.b > y.b;
    else return x.d < y.d;
}
int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	for (int i=1;i<=n;++i)
	  scanf("%d",&a[i].d);
	for (int i=1;i<=n;++i)
	  scanf("%d",&a[i].b);
    sort(a+1,a+n+1,cmp);//  
	memset(f,200,sizeof(f));
	for (int i=1;i<=n;++i)
	{
		f[i-1][0]=0;
		for (int j=1;j<=m;++j)
			f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i].d-a[i].b*(j-1));
	}
    printf("%d",f[n][m]);
	return 0;
}

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

현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다