hiho一下 第173周
2024-09-07 15:30:36
题目1 : A Game
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Little Hi and Little Ho are playing a game. There is an integer array in front of them. They take turns (Little Ho goes first) to select a number from either the beginning or the end of the array. The number will be added to the selecter's score and then be removed from the array.
Given the array what is the maximum score Little Ho can get? Note that Little Hi is smart and he always uses the optimal strategy.
输入
The first line contains an integer N denoting the length of the array. (1 ≤ N ≤ 1000)
The second line contains N integers A1, A2, ... AN, denoting the array. (-1000 ≤ Ai ≤ 1000)
输出
Output the maximum score Little Ho can get.
- 样例输入
-
4
-1 0 100 2 - 样例输出
-
99 AC代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int a[], dp[][], s[];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
memset(dp, , sizeof(dp));
s[] = ;
s[] = a[];
for (int i = ; i <= n; i++) {
s[i] = s[i - ] + a[i];
}
for (int i = ; i <= n; i++) {
dp[i][i] = a[i];
dp[i][i + ] = a[i] > a[i + ] ? a[i] : a[i + ];
}
for (int i = n; i >= ; i--) {
for (int j = i + ; j <= n; j++) {
dp[i][j] = dp[i + ][j] > dp[i][j - ] ? s[j] - s[i - ] - dp[i][j - ] : s[j] - s[i - ] - dp[i + ][j];
}
}
printf("%d\n", dp[][n]);
return ;
}WA代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int a[], dp[][], s[];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
memset(dp, , sizeof(dp));
s[] = ;
s[] = a[];
for (int i = ; i <= n; i++) {
s[i] = s[i - ] + a[i];
}
for (int i = ; i <= n; i++) {
dp[i][i] = a[i];
dp[i][i + ] = a[i] > a[i + ] ? a[i] : a[i + ];
}
for (int i = ; i <= n; i++) {
for (int j = ; j + i - <= n; j++) {
int tmp = -;
//j+1->j+i-1
if (a[j] + (s[j + i - ] - s[j]) - dp[j + ][j + i - ] > tmp) {
tmp = a[j] + (s[j + i - ] - s[j]) - dp[j + ][j + i - ];
}
//j->j+i-2
if (a[j + i - ] + (s[j + i - ] - s[j - ]) - dp[j][j + i - ] > tmp) {
tmp = a[j + i - ] + (s[j + i - ] - s[j - ]) - dp[j][j + i - ];
}
dp[j][j + i - ] = tmp;
}
}
printf("%d\n", dp[][n]);
return ;
}思路一样,就是不知道为什么不对。
几个小时之后,两种都不对了。那你特么倒是解释解释这是怎么回事啊?
真操蛋,这种问题遇到无数次了。
OK了,辣鸡OJ评测机有问题。
最新文章
- 萌新笔记——Cardinality Estimation算法学习(二)(Linear Counting算法、最大似然估计(MLE))
- html的a标签display:block之后文字竖直居中
- python 安装模块
- 阿里云消息队列MQ_HTTP接入 for .NetCore 简单例子
- STRUTS2 嵌套循环
- (06)odoo报表
- 一起来画画!8款最佳HTML5绘图工具
- AXURE制作APP抽屉式菜单
- 深入理解计算机系统第二版习题解答CSAPP 2.14
- JS 用角度换东南西北
- CentOS 安装Chrome
- 学习总结---SNAT和DNAT
- 使用c语言实现linux数据库的操作
- Image和Base64互相转换
- mysql tablespace(独立表空间)超速备份大数据
- Java整理
- nginx配置url中带问号的rewrite跳转
- JMS学习(七)-ActiveMQ消息的持久存储方式之KahaDB存储
- sftp命令不被识别
- 如何将.NET 4.0写的Windows service和Web API部署到docker上面