Problem 1538 - B - Stones II(동적 계획)
3525 단어 동적 기획
Time Limit: 1000MS Memory Limit: 65536KB
Total Submit: 371 Accepted: 54 Special Judge: No
Description
Xiaoming took the flight MH370 on March 8, 2014 to China to take the ACM contest in WHU. Unfortunately, when the airplane crossing the ocean, a beam of mystical light suddenly lit up the sky and all the passengers with the airplane were transferred to another desert planet.
When waking up, Xiaoming found himself lying on a planet with many precious stones. He found that:
There are n precious stones lying on the planet, each of them has 2 positive values ai and bi. Each time Xiaoming can take the ith of the stones ,after that, all of the stones’ aj (NOT including the stones Xiaoming has taken) will cut down bi units.
Xiaoming could choose arbitrary number (zero is permitted) of the stones in any order. Thus, he wanted to maximize the sum of all the stones he has been chosen. Please help him.
Input
The input consists of one or more test cases.
First line of each test case consists of one integer n with 1 <= n <= 1000.
Then each of the following n lines contains two values ai and bi.( 1<= ai<=1000, 1<= bi<=1000)
Input is terminated by a value of zero (0) for n.
Output
For each test case, output the maximum of the sum in one line.
Sample Input
1
100 100
3
2 1
3 1
4 1
0
Sample Output
100
6
dp[i][j]: 이전 i항목에서 j항목의 최대값을 선택합니다.
dp[i][j]=max(dp[i-1][j],dp[i][j-1]+p[i].ai-p[i].bi*(j-1))
#include<bits/stdc++.h>
//#include<iostream>
//#include<cmath>
//#include<cstring>
//#include<string>
//#include<cstdlib>
//#include<cstdio>
//#include<map>
//#include<algorithm>
using namespace std;
template<class T>inline T read(T&x)
{
char c;
while((c=getchar())<=32);
bool ok=false;
if(c=='-')ok=true,c=getchar();
for(x=0; c>32; c=getchar())
x=x*10+c-'0';
if(ok)x=-x;
return x;
}
template<class T> inline void read_(T&x,T&y)
{
read(x);
read(y);
}
template<class T> inline void read__(T&x,T&y,T&z)
{
read(x);
read(y);
read(z);
}
template<class T> inline void write(T x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
write(x);
putchar('
');
}
//-------ZCC IO template------
const int maxn=1001;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long LL;
typedef double DB;
#define bug printf("---
");
struct node
{
int ai,bi;
bool operator<(node tmp)const
{
if(tmp.bi!=bi)return bi>tmp.bi;
else return ai>tmp.ai;
}
}p[maxn];
int dp[maxn][maxn];
int main()
{
int n;
while(read(n))
{
for(int i=1;i<=n;i++)
{
read_(p[i].ai,p[i].bi);
}
sort(p+1,p+n+1);
For(i,0,n+1)dp[i][0]=0;
For(i,1,n+1)For(j,1,i+1)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+p[i].ai-(j-1)*p[i].bi);
}
int ans=0;
For(i,0,n+1)
ans=max(ans,dp[n][i]);
writeln(ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.