哪些品牌网站做的好,优化网站步骤,公众号文章模板素材,网页设计作品要求题面 给你一个n*m的矩阵#xff0c;要求每一行选择一个数#xff0c;并且第i行选择的位置a[i]一定要大于第i-1行选择的位置a[i-1]#xff0c;求选取的数的总和为多少#xff0c;输出一组字典序最小的a[1]到a[n]。1nm100 链接#xff1a;http://contest-hunter…题面 给你一个n*m的矩阵要求每一行选择一个数并且第i行选择的位置a[i]一定要大于第i-1行选择的位置a[i-1]求选取的数的总和为多少输出一组字典序最小的a[1]到a[n]。1nm100 链接http://contest-hunter.org/contest/0x5E 思路 首先dp的状态是显而易见的 \(f[i][j]\max_{i-1kj}f[i-1][k]a[i][j]\) 表示选到第i行第j个数且一定会选这个数时的和的最大值。复杂度是\(O(n^3)\)虽然可以过但其实还可以优化可以发现k的范围是随j不断变大的所以每一次循环i时设一个变量maxk然后j每改变一次就用f[i-1][j-1]更新一次maxk就可以了。 实际上这种优化相当于一个表示选到第i行第j个数且不一定会选这个数时的和的最大值的状态只需要改一下转移方程就好了 \(f[i][j]\max\{f[i][j-1],f[i-1][j-1]a[i][j]\}\) 至于到底怎么设好因人而异了只是有时候设第一种类型设多了就不记得设第二种了_还是都练练为好。 代码 #include cstring
using namespace std;
const int N110;
typedef long long ll;
int p[N][N],a[N][N];
ll f[N][N];
void dfs(int i,int j)
{if(!i) return;dfs(i-1,p[i][j]);printf(%d ,j);
}
int main()
{int n,m,jj;scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j)scanf(%d,a[i][j]);memset(f,0xc0,sizeof(f));ll ansf[0][0];f[0][0]0;for(int i1;in;i){int maxif[i-1][i-1],iii-1;for(int ji;jm;j){f[i][j]maxia[i][j];p[i][j]ii;if(maxif[i-1][j]) maxif[i-1][j],iij;}}for(int in;im;i)if(ansf[n][i]) ansf[n][i],jji;printf(%lld\n,ans);dfs(n,jj);putchar(\n);return 0;
} 转载于:https://www.cnblogs.com/flashlizard/p/10995228.html
