LS 21 Packing(DP)
Packing
The cost of set {(a1,b1),(a2,b2),…,(an,bn)} is defined as
max{ai}×max{bi}
Partition set {(a1,b1),(a2,b2),…,(an,bn)} into several non-empty subsets to minimize the sum of the cost of subsets.
Input
The first line contains an integer n .
n lines follow. Each of them contains two integer ai,bi .
(1≤n≤1000,1≤ai,bi≤1000)
Ouptut
Single integer denotes the minimum value.
Sample input
3
1 1
1 3
3 1Sample output
6Note
Partition {{(1,1),(1,3)},{(3,1)}} gives the cost of 1×3+3×1=6 . 사고방식: 수조 maxn[x][y]로 x에서 y까지 가장 큰 b를 나타낸다.a는 그냥 서열을 정하면 돼요.
dp[x]는 정렬된 전 x조의 최우수값을 나타낸다.dp[x]=min(dp[x],maxn[j][i]*a[i]){j<=i}a[i]는 순서가 끝난 후입니다.
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=1010;
const int oo=1e9;
class node
{
public:int a,b;
}f[mm];
int dp[mm],maxn[mm][mm];
int n;
bool cmp(node a,node b)
{ if(a.a^b.a)
return a.a<b.a;
return a.b<b.b;
}
int main()
{
while(cin>>n)
{
for(int i=1;i<=n;i++)
cin>>f[i].a>>f[i].b;
sort(f+1,f+n+1,cmp);/// a
memset(maxn,0,sizeof(maxn));
for(int i=1;i<=n;i++)/// b
{ maxn[i][i]=f[i].b;
for(int j=i+1;j<=n;j++)
maxn[i][j]=maxn[i][j-1]>f[j].b?maxn[i][j-1]:f[j].b;
}
dp[0]=0;
for(int i=1;i<=n;i++)
{ dp[i]=oo;int z;
for(int j=1;j<=i;j++)
{ z=maxn[i-j+1][i]*f[i].a+dp[i-j];
if(dp[i]>z)dp[i]=z;
}
}
cout<<dp[n]<<"
";
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
