当前位置:网站首页>POJ 3176 cow bowling (DP | memory search)
POJ 3176 cow bowling (DP | memory search)
2022-07-05 11:28:00 【Full stack programmer webmaster】
Cow Bowling
Time Limit: 1000MS | Memory Limit: 65536K | |
---|---|---|
Total Submissions: 14210 | Accepted: 9432 |
Description
The cows don’t use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Then the other cows traverse the triangle starting from its tip and moving “down” to one of the two diagonally adjacent cows until the “bottom” row is reached. The cow’s score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.
Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.
Output
Line 1: The largest sum achievable using the traversal rules
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Number triangle problem .. Able to sit from bottom to top dp dp[i][j]=ma[i][j]+max(dp[i+1][j],dp[i+1][j+1])
Giant water .. Think of my ignorant brush six months ago dp I don't know anything .. Ah What a sad story ..
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 360
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,dp[maxn][maxn],ma[maxn][maxn];
void solve()
{
for(int i=0;i<n;i++)
dp[n-1][i]=ma[n-1][i];
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)
dp[i][j]=max(ma[i][j]+dp[i+1][j],ma[i][j]+dp[i+1][j+1]);
printf("%d\n",dp[0][0]);
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
scanf("%d",&ma[i][j]);
memset(dp,0,sizeof(dp));
solve();
}
return 0;
}
It can also be memorized from top to bottom Search for .. Then the meaning of the state array is almost the same .. Personally, I think search is easier to write ...
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 360
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,dp[maxn][maxn],ma[maxn][maxn];
int dfs(int x,int y)
{
if(x==n-1)return ma[x][y];
if(dp[x][y]>=0)return dp[x][y];
dp[x][y]=0;
dp[x][y]+=(ma[x][y]+max(dfs(x+1,y),dfs(x+1,y+1)));
return dp[x][y];
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
scanf("%d",&ma[i][j]);
memset(dp,-1,sizeof(dp));
printf("%d\n",dfs(0,0));
}
return 0;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/109498.html Link to the original text :https://javaforall.cn
边栏推荐
- Msfconsole command encyclopedia and instructions
- [crawler] Charles unknown error
- COMSOL -- establishment of geometric model -- establishment of two-dimensional graphics
- 【爬虫】charles unknown错误
- 修复动漫1K变8K
- [crawler] bugs encountered by wasm
- Zcmu--1390: queue problem (1)
- In the last process before the use of the risk control model, 80% of children's shoes are trampled here
- Characteristics and electrical parameters of DDR4
- Startup process of uboot:
猜你喜欢
Modulenotfounderror: no module named 'scratch' ultimate solution
Harbor image warehouse construction
COMSOL--三维图形的建立
DDRx寻址原理
AutoCAD -- mask command, how to use CAD to locally enlarge drawings
7.2 daily study 4
DDR4硬件原理图设计详解
The ninth Operation Committee meeting of dragon lizard community was successfully held
Codeforces Round #804 (Div. 2)
Lombok 同时使⽤@Data和@Builder 的坑,你中招没?
随机推荐
【爬虫】wasm遇到的bug
sklearn模型整理
[crawler] Charles unknown error
spark调优(一):从hql转向代码
Sklearn model sorting
如何让全彩LED显示屏更加节能环保
Stop saying that microservices can solve all problems!
SLAM 01. Modeling of human recognition Environment & path
How can China Africa diamond accessory stones be inlaid to be safe and beautiful?
COMSOL--建立几何模型---二维图形的建立
Msfconsole command encyclopedia and instructions
shell脚本文件遍历 str转数组 字符串拼接
SET XACT_ABORT ON
【爬虫】charles unknown错误
How does redis implement multiple zones?
MFC pet store information management system
Spark Tuning (I): from HQL to code
Pytorch training process was interrupted
OneForAll安装使用
Three suggestions for purchasing small spacing LED display