当前位置:网站首页>DP - [noip2000] grid access
DP - [noip2000] grid access
2022-04-23 14:13:00 【Stingy old Sao】
[NOIP2000] Take the number of squares
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
//
Space 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
//
版权声明
本文为[Stingy old Sao]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231407093939.html
边栏推荐
- 拨开云雾synchronized使用五种方式介绍
- Jacob print word
- Wechat applet obtains login user information, openid and access_ token
- Switch usage (wechat applet)
- RobotFramework 之 文件上传和下载
- 01-nio basic ByteBuffer and filechannel
- JSP学习2
- Research on recyclerview details - Discussion and repair of recyclerview click dislocation
- ActiveMQ Basics
- 快速搞懂线程实现的三种方式
猜你喜欢
什么是云迁移?云迁移的四种模式分别是?
金融行业云迁移实践 平安金融云整合HyperMotion云迁移解决方案,为金融行业客户提供迁移服务
政务云迁移实践 北明数科使用HyperMotion云迁移产品为某政府单位实施上云迁移项目,15天内完成近百套主机迁移
线程组ThreadGroup使用介绍+自定义线程工厂类实现ThreadFactory接口
某政务云项目业务系统迁移调研实践
帆软实现一个单选按钮,可以统一设置其他单选按钮的选择状态
HyperMotion云迁移完成阿里云专有云产品生态集成认证
帆软报表设置单元格填报以及根据值的大小进行排名方法
星界边境文本自动翻译机使用说明
困扰多年的系统调研问题有自动化采集工具了,还是开源免费的
随机推荐
sql中出现一个变态问题
返回数组排序后下标
01-nio basic ByteBuffer and filechannel
帆软中使用if else 进行判断-使用标题条件进行判断
Gartner预测云迁移规模大幅增长;云迁移的优势是什么?
使用Executors类快速创建线程池
Wechat applet initializes Bluetooth, searches nearby Bluetooth devices and connects designated Bluetooth (I)
星界边境Starbound创意工坊订阅的mod的存放路径
VMWare安装64位XP中文教程
政务云迁移实践 北明数科使用HyperMotion云迁移产品为某政府单位实施上云迁移项目,15天内完成近百套主机迁移
更改plsql工具栏的图标大小
关于训练过程中损失函数出现断崖式增长的问题
01-NIO基础之ByteBuffer和FileChannel
星界边境文本自动翻译机(高级版)使用说明
Operation instructions of star boundary text automatic translator
Subscription number development of wechat applet (message push)
Logback logger and root
ActiveMq基础知识
HyperMotion云迁移完成阿里云专有云产品生态集成认证
Pycharm连接远程服务器并实现远程调试