先打一个最裸的暴力再优化 10分代码
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 105 using namespace std; int n,m,a[N][N],true_ans,choose[N]; //n束花 m个瓶子 vector <int> q; void dfs(int now,int bottle,int ans,vector<int> v) { // cout<<now<<" "<<bottle<<" "<<ans<<en if(now==n) { if(ans>true_ans) { true_ans=ans; for(int i=0;i<n;i++) { choose[i]=v[i]; } } return; } for(int i=bottle+1;i<=m;i++) { v.push_back(i); dfs(now+1,i,ans+a[now+1][i],v); v.pop_back(); } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=m;i++) { q.push_back(i); dfs(1,i,a[1][i],q); q.pop_back(); } cout<<true_ans<<endl; for(int i=0;i<n;i++) { cout<<choose[i]<<" "; } return 0; }然后我们发现 我们可以记忆一束花i 插在瓶子j的最优值 这样就跑的跟香港记者一样快了
#include<bits/stdc++.h> #define N 105 #define INF 0x7ffffff using namespace std; int st; int n,m,a[N][N],true_ans,choose[N][N],f[N][N]; int dfs(int now,int last) //第i朵花 上一次插last { if(now>n) return 0; if(f[now][last]) return f[now][last]; int tmp=-INF; for(int i=last+1;i<=m;i++) { int x=dfs(now+1,i)+a[now][i]; if(x>tmp) { tmp=x; choose[now][last]=i; } } return f[now][last]=tmp; } inline void find(int now,int last) { if(now>n) return; cout<<choose[now][last]<<" "; find(now+1,choose[now][last]); } int main() { st=clock(); cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } cout<<dfs(1,0)<<endl; find(1,0); return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9809339.html
