題目描述

農歷新年馬上就要到了，奶牛們計劃舉辦一次聚會慶祝新年的到來。但是，奶牛們并不喜歡走太遠的路，這會給他們的聚會帶來消極情緒，當一頭奶牛的消極指數為Wi，他參加聚會所需行走的距離為si，那么他就會給聚會帶來Si3*Wi的消極情緒。所有奶牛所在位置都在一條直線上，已知所有奶牛的坐標和消極指數，求如何確定聚會地點，使得所有奶牛給聚會帶來的消極情緒之和最小，輸出消極情緒之和的最小值。

輸入

第一行包含一個整數 Ca(Ca<=20) ，表示有 Ca 組測試數據。
對于每組測試數據：第一行包含一個整數n(1<=n<=50000) ，表示奶牛的數量。接下來 n 行每行包含兩個浮點數Si和wi (-106<=Si<=106, 0<Wi<15)。

輸出

對于每組測試數據，輸出 “Case #c: ans” ，其中c表示測試數據編號，ans表示消極情緒之和的最小值，結果四舍五入為一個整數。

樣例輸入

1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2

樣例輸出

Case #1: 300

dp問題 c++實現：

#include<iostream> #include<cmath> typedef long long ll; using namespace std; double x[50005][2]; int n; double cal(double a){double sum=0;for(int i=0;i<n;i++){sum+=fabs(x[i][0]-a)*fabs(x[i][0]-a)*fabs(x[i][0]-a)*x[i][1];}return sum; } int main(){int t;cin>>t;for(int w=1;w<=t;w++){cin>>n;for(int i=0;i<n;i++)cin>>x[i][0]>>x[i][1];double a=-1000000,b=1000000;while(a-b<0.00001){double L=a+(b-a)/3;double r=b-(b-a)/3;if(cal(L)<cal(r)) b=r;else a=L;}cout<<"Case #"<<w<<": "<<(ll)(cal(a)+0.5)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Dp问题：奶牛的聚会的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。