原题链接:信息学奥赛一本通T1279-橱窗布置
解题思路:
由于本人不会dp所以来一发dfs解题,哈哈哈
注意事项:
参考代码:
#include"bits/stdc++.h" using namespace std; #define ll long long #define endl '\n' const ll N=105; ll f,v,kkk; ll a[N][N]; ll b[N][N]; vector<ll> v1,v2; void dfs(ll x,ll y,ll sum){ if(x>=f+1){//递归结束条件,注意是f+1 if(sum>kkk){ kkk=sum; v2=v1; } return; } if(b[x][y]>=sum)return;//剪枝 b[x][y]=sum;//记录最优值 for(ll i=y;i<=v;i++){ v1.push_back(i); dfs(x+1,i+1,sum+a[x][i]); v1.pop_back(); } } int main(){ cin>>f>>v; memset(b,-0x3f,sizeof b); for(ll i=1;i<=f;i++){ for(ll j=1;j<=v;j++){ cin>>a[i][j]; } } dfs(1,1,0); cout<<kkk<<endl; for(auto i:v2)cout<<i<<' '; return 0; }
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复