Codeforces Round #584 E2. Rotate Columns (hard version)
2024-09-05 04:15:23
链接:
https://codeforces.com/contest/1209/problem/E2
题意:
This is a harder version of the problem. The difference is only in constraints.
You are given a rectangular n×m matrix a. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.
After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for i-th row it is equal ri. What is the maximal possible value of r1+r2+…+rn?
思路:
考虑状压DP, Dp[i][j], 表示已经对i列操作, 同时行状态为j的最大值.
枚举每列, 枚举每列的选行状态, 跟之前不冲突的状态比较.
枚举结束后转移状态,同时考虑可以选列最大值最大的n个列, 减少范围.
DP还是难啊
代码:
#include <bits/stdc++.h>
using namespace std;
int Dp[(1<<12)+10], Tmp1[(1<<12)+10], Tmp2[(1<<12)+10];
int a[20][2010], Id[2010], Val[2010];
int n, m;
bool Cmp(int l, int r)
{
if (Val[l] > Val[r])
return true;
return false;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(Val, 0, sizeof(Val));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
Id[j] = j;
Val[j] = max(Val[j], a[i][j]);
}
}
sort(Id + 1, Id + 1 + m, Cmp);
m = min(n, m);
memset(Dp, 0, sizeof(Dp));
for (int i = 1; i <= m; i++)
{
memcpy(Tmp2, Dp, sizeof(Dp));
memset(Tmp1, 0, sizeof(Tmp1));
for (int ti = 0; ti < n; ti++)
{
for (int s = 0; s < (1 << n); s++)
Tmp2[s] = Dp[s];
for (int s = 0; s < (1 << n); s++)
{
for (int li = 0; li < n; li++)
{
if (!((1 << li) & s))
Tmp2[s | (1 << li)] = max(Tmp2[s | (1 << li)], Tmp2[s] + a[(ti + li) % n][Id[i]]);
}
}
for (int s = 0; s < (1 << n); s++)
Tmp1[s] = max(Tmp1[s], Tmp2[s]);
}
// for (int s = 0;s < (1 << n); s++)
// cout << Tmp1[s] << ' ' ;
// cout << endl;
for (int s = 0;s < (1 << n); s++)
Dp[s] = Tmp1[s];
}
printf("%d\n", Dp[(1<<n)-1]);
}
return 0;
}
最新文章
- ASP.NET MVC——CodeFirst开发模式
- Mac 下面 apache 不解析PHP(or PHP 版本不对)的解决办法
- .NET魔法堂:工程构建基石->;MSBuild
- C语言中常量
- Gedit中文乱码
- Nmap备忘单:从探索到漏洞利用 Part1
- ASP.NET MVC系列 框架搭建(二)之仓储层的优化
- js里的匿名函数 数组排序
- # 20145210 《Java程序设计》第06周学习总结
- Android注解利器:ButterKnife 的基本使用
- js 常用插件
- params SqlParameter[] commandParameters(转)
- Machine Learning|Andrew Ng|Coursera 吴恩达机器学习笔记
- CRM客户关系管理系统(十)
- Index API
- centos下安装python3.7.0以上版本时报错ModuleNotFoundError: No module named &#39;_ctypes&#39;
- spring Cache注解详解
- JS Math方法
- nodejs故障cnpm没反应
- Eclipse neon 4.6 安装tomcat