博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BUCT-OJ 2052 数字三角形2
阅读量:5867 次
发布时间:2019-06-19

本文共 1458 字,大约阅读时间需要 4 分钟。

【题目来源】:TYVJ 1076

【题目链接】:

 

【解题思路】:

刚开始没想到思路,想到暴力穷举会超时,就乖乖的使用动态规划,但怎么使用想的一团,晕了,

真正独立做起题目来感觉动态规划还没入门的样子,就又重新从最基础的一点点向上想,首先动态规划最起码得有状态吧,

那对应与每一个权值的状态是什么?感觉有很多种情况,没办法了,我穷举所有状态还不行吗,突然发现是mod100的,那一

个权值最多就是100种情况了, 最多25行(1+2+...+25)*100=32500种情况,完全可以穷举。所以开一个三位数组arr[26][26][101],问题得解。

 

A C代码】:

#include 
#include
#include
using namespace std; int arr[26][26]; int flag[26][26][101]; int main() { int n, i, j, k; while(~scanf("%d", &n)) { memset(arr, 0, sizeof(arr)); memset(flag, 0, sizeof(flag)); for(i = 1; i <= n; i++) for(j = 1; j <= i; j++) scanf("%d", &arr[i][j]); flag[1][1][arr[1][1] % 100] = 1; for(i = 2; i <= n; i++) { for(j = 1; j <= i; j++) { for(k = 0; k < 100; k++) { if(flag[i-1][j-1][k]) flag[i][j][(k + arr[i][j]) % 100] = 1; if(flag[i-1][j][k]) flag[i][j][(k + arr[i][j]) % 100] = 1; } } } int ans = -1; for(j = 1; j <= n; j++) for(k = 0; k < 100; k++) if(flag[n][j][k]) { if(k > ans) ans = k; } printf("%d\n", ans); } }

 

转载于:https://www.cnblogs.com/litaotao/archive/2013/05/19/3592477.html

你可能感兴趣的文章
git diff 的用法
查看>>
你不知道的Virtual DOM(二):Virtual Dom的更新
查看>>
CentOS 6.5搭建ELK环境ElasticSearch+Kibana+Logstash
查看>>
前端性能优化小结
查看>>
ubuntu中安装oracle 11g
查看>>
MacBook如何用Parallels Desktop安装windows7/8
查看>>
gitlab 完整部署实例
查看>>
GNS关于IPS&ASA&PIX&Junos的配置
查看>>
七天学会ASP.NET MVC (四)——用户授权认证问题
查看>>
upgrade to iOS7,how to remove stroyboard?
查看>>
影响企业信息化成败的几点因素
查看>>
Clipboard 实现网页复制粘贴
查看>>
Thinkphp5 模型里别名alias不生效bug【已解决】
查看>>
System Center Virtual Machine Manager 2012 RC– Evaluation
查看>>
Access数据类型与.net OleDbType枚举类型的对应
查看>>
SCCM 2016 配置管理系列(Part8)
查看>>
给在生产环境下给php安装apc加速扩展脚本
查看>>
as3.0 切分位图
查看>>
zabbix监控部署
查看>>
关于Tomcat下项目中文名在Windows和Linux下编码混乱问题解决
查看>>