当前位置:网站首页>dp-[NOIP2000]方格取数
dp-[NOIP2000]方格取数
2022-04-23 14:08:00 【抠脚老騷】
[NOIP2000]方格取数
n^4
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
const int maxn = 1e2 + 10;
const int N = 6e6 + 100;
int dp[maxn][maxn][maxn][maxn];
int a[maxn][maxn];
int v[maxn];
void solve() {
int n;
cin >> n;
int x, y, w;
while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
dp[1][1][1][1] = a[1][1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
for (int g = 1; g <= n; g++) {
// if (i + j != k + g) continue;
int ans = a[i][j] + a[k][g];
if (i == k && j == g) ans /=2;
dp[i][j][k][g] = max(dp[i][j][k][g], dp[i - 1][j][k - 1][g] + ans);
dp[i][j][k][g] = max(dp[i][j][k][g], dp[i][j - 1][k - 1][g] + ans);
dp[i][j][k][g] = max(dp[i][j][k][g], dp[i - 1][j][k][g - 1] + ans);
dp[i][j][k][g] = max(dp[i][j][k][g], dp[i][j - 1][k][g - 1] + ans);
// cout<<dp[i][j][k][g]<<endl;
}
cout << dp[n][n][n][n];
}
signed main() {
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();//cout<<"\n";
}
return 0;
}
//12341
//14321
//
n^3
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
const int maxn = 1e2 + 10;
const int N = 6e6 + 100;
int dp[maxn][maxn][maxn];
int a[maxn][maxn];
int v[maxn];
void solve() {
int n;
cin >> n;
int x, y, w;
while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
dp[2][1][1] = a[1][1];
for (int i = 2; i <= 2*n; i++)
for (int k = 1; k <= n; k++)
for (int g = 1; g <= n; g++) {
int x1=k,x2=g,y1=i-k,y2=i-g;
int ans=a[x1][y1]+a[x2][y2];
if(x1==x2&&y1==y2) ans/=2;
dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1-1][x2]);
dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1][x2-1]);
dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1][x2]);
dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1-1][x2-1]);
}
cout << dp[2*n][n][n];
}
signed main() {
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();//cout<<"\n";
}
return 0;
}
//12341
//14321
//
空间n^2
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
const int maxn = 1e2 + 10;
const int N = 6e6 + 100;
int dp[maxn][maxn];
int a[maxn][maxn];
int v[maxn];
void solve() {
int n;
cin >> n;
int x, y, w;
while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
for (int i = 2; i <= 2*n; i++)
for (int k=i; k>0; k--)
for (int g=i; g>0; g--) {
int x1=k,x2=g,y1=i-k,y2=i-g;
int ans=a[x1][y1]+a[x2][y2];
if(x1==x2&&y1==y2) ans/=2;
dp[k][g]=max(max(dp[k-1][g],dp[k][g-1]),max(dp[k-1][g-1],dp[k][g]))+ans;
// cout<<dp[k][g]<<endl;
}
cout << dp[n][n];
}
signed main() {
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();//cout<<"\n";
}
return 0;
}
//12341
//14321
//
版权声明
本文为[抠脚老騷]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_45436102/article/details/123998306
边栏推荐
- 帆软实现分页时第一行和最后两行冻结方式
- Recyclerview advanced use (I) - simple implementation of sideslip deletion
- Nifi 快速安装及文件同步操作
- MySQL数据库讲解(十)
- 使用Postman进行Mock测试
- 帆软中单元格中隔行变色以及数量大于100字体变大变红设置
- FBS (fman build system) packaging
- Logging module
- Wechat applet initializes Bluetooth, searches nearby Bluetooth devices and connects designated Bluetooth (I)
- Call wechat customer service applet
猜你喜欢
Indoor and outdoor map switching (indoor three-point positioning based on ibeacons)
帆软调用动态传参的方法,在标题中设置参数
帆软报表设置单元格填报以及根据值的大小进行排名方法
VMware installation 64 bit XP Chinese tutorial
org.apache.parquet.schema.InvalidSchemaException: A group type can not be empty. Parquet does not su
帆软之单元格部分字体变颜色
Cdh6 based on CM management 3.2 cluster integration atlas 2 one
Idea控制台乱码解决
星界边境Starbound创意工坊订阅的mod的存放路径
更改plsql工具栏的图标大小
随机推荐
Operation instructions of star boundary text automatic translator
postman批量生产body信息(实现批量修改数据)
查询2013年到2021年的数据,只查询到2020的数据,遇到了这个问题所进行的解决办法
利用json-server在本地创建服务器请求
关于Jmeter启动闪退问题
VMware 15pro mounts the hard disk of the real computer in the deepin system
RobotFramework 之 文件上传和下载
使用DialogFragment的一些感受及防踩坑经验(getActivity、getDialog为空,cancelable无效等)
使用itextpdf实现截取pdf文档第几页到第几页,进行分片
百度图片识别自定义实现(替代AipOcr)
JSP学习2
win10自带Groove音乐不能播放CUE和APE文件的一种曲线救国办法,自己创建aimppack插件包,AIMP安装DSP插件
帆软中根据分类进行汇总
ActiveMq基础知识
线程间控制之Semaphore使用介绍
容灾有疑问?点这里
MySQL数据库讲解(七)
Nifi 快速安装及文件同步操作
sql中出现一个变态问题
HyperBDR云容灾V3.2.1版本发布|支持更多云平台,新增监控告警功能