M-SOLUTIONS Programming Contest 2020 E.M‘s Solution

M-SOLUTIONS Programming Contest 2020 E.M’s Solution

题目链接

比赛时完全没思路，吐了，结果可以 DFS？不会爆掉吗……结果 $1$s 都没有就过了，所以告诫我们要勇于尝试，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int n;
ll x[15],y[15],p[15],res[20][20],ans[20];
void dfs(int i,int num){if(i==n){ans[num]=min(ans[num],accumulate(res[n],res[n]+n,0LL));return ;}for(int j=0;j<n;j++) res[i+1][j]=res[i][j];dfs(i+1,num);for(int j=0;j<n;j++) res[i+1][j]=min(res[i][j],p[j]*abs(x[j]-x[i]));dfs(i+1,num+1);for(int j=0;j<n;j++) res[i+1][j]=min(res[i][j],p[j]*abs(y[j]-y[i]));dfs(i+1,num+1);
}int main(){cin>>n;for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>p[i];for(int j=0;j<n;j++){res[0][j]=p[j]*min(abs(x[j]),abs(y[j]));ans[j]=INF;}dfs(0,0);for(int i=0;i<=n;i++) cout<<ans[i]<<endl;return 0;
}