本文共 650 字，大约阅读时间需要 2 分钟。

因为雕像一定是重量从小到大放过来的

所以只要直到之前放了几个雕像,就直到现在要放什么雕像

定义$f[i][j]$表示前$i$个位置放了$j$个雕像的最小代价

一个简简单单的$O(n^2)$的$dp$就搞定了

#include 
   
    using namespace std;#define int long longint n,k,f[5009][5009];typedef pair
    
     p;vector
     
vec;signed main(){
   	cin >> n >> k;	for(int i=1;i<=k;i++)	{
   		p now; scanf("%lld%lld",&now.second,&now.first );		vec.push_back( now );	}	sort( vec.begin(),vec.end() );	memset( f,0x3f,sizeof f );	for(int i=0;i<=n;i++)	f[i][0] = 0;	for(int i=1;i<=n;i++)	for(int j=1;j<=i && j<=k;j++)		f[i][j] = min( f[i-1][j],f[i-1][j-1]+vec[j-1].first*abs(i-vec[j-1].second) );	cout << f[n][k];}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/117453292 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！