BZOJ 3997 [TJOI 2015 组合数学] 解题报告
2024-10-15 04:26:49
这个题我脑洞了一个结论:
首先,我们定义满足以下条件的路径为“从右上到左下的路径”:
对于路径上任何不相同的两个点 $(x_1, y_1)$,$(x_2, y_2)$,都有:
- $x_1\neq x_2, y_1\neq y_2$
- 若 $x_1 > x_2$,则有 $y_1 < y_2$;否则当 $x_1 < x_2$ 时, $y_1 > y_2$。
然后我们找到所有从右上到左下的路径,其中路径的权值和最大的那条路径的权值和就是答案了。
然后我们就可以用 Dp 解决问题了。
我们可以把每一行都翻转一下,那么就可以有:
$$Dp[i][j] = max(Dp[i - 1][j - 1] + W[i][j], Dp[i - 1][j], Dp[i][j - 1])$$
其中 $W[i][j]$ 为这个格子的权值,那么答案就是 $Dp[n][m]$ 了。
至于为什么是对的。。。我也不太清楚。。。反正感觉好像是对的。。。而且也过了。。。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000 + 5 int n, m, ans;
int Map[N][N], Dp[N][N]; inline int getint()
{
char ch = '\n';
for (; ch > '' || ch < ''; ch = getchar()) ;
int res = ch - '';
for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())
res = (res << ) + (res << ) + ch - '';
return res;
} inline void Solve()
{
n = getint(), m = getint();
for (int i = ; i <= n; i ++)
for (int j = m; j; j --)
Map[i][j] = getint();
for (int i = ; i <= n; i ++)
for (int j = ; j <= m; j ++)
{
Dp[i][j] = Dp[i - ][j - ] + Map[i][j];
Dp[i][j] = max(Dp[i][j], Dp[i - ][j]);
Dp[i][j] = max(Dp[i][j], Dp[i][j - ]);
}
ans = Dp[n][m];
} int main()
{
#ifndef ONLINE_JUDGE
freopen("3997.in", "r", stdin);
freopen("3997.out", "w", stdout);
#endif for (int _ = getint(); _; _ --)
{
Solve();
printf("%d\n", ans);
} #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
3997_Gromah
最新文章
- EST
- 重温Bootstrap
- Activity启动模式
- 编译iOS程序时的-all_load选项,以及-all_load 导致的 ld duplicate symbol xx的问题
- Samy XSS Worm之源码讲解
- 使用angular.js开发的一个简易todo demo
- (转载)Linux下安装配置MySQL+Apache+PHP+WordPress的详细笔记
- Android Touch系统简介(二):实例详解onInterceptTouchEvent与onTouchEvent的调用过程
- 【.NET-MVC】ASP.NET MVC学习笔记1-概述
- Spring AOP中 args和arg-names的区别
- 关于jstl的使用
- ThinkPHP5零基础搭建CMS系统(一)
- EF的应用
- sql server 日志文件结构及误操作数据找回
- 讲解wpe抓包,封包
- (数据存储)Android系统存储数据
- 图片识别文字, OCR
- SparkStreaming 的编程模型
- 解析KML文件并提取coordinates中的经纬度坐标信息
- Spring启动时获取自定义注解的属性值