Light oj 1125 - Divisible Group Sums (dp)
2024-09-05 03:18:58
题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1125
题意:
给你n个数,q次询问,每次询问问你取其中m个数是d的整数倍的方案数。
题意:
dp[i][j][k] 表示前i个数, %d=j, 取了k个的方案数。
ID | SUBMISSION TIME | PROBLEM | SOURCE | CPU | MEMORY | VERDICT |
---|---|---|---|---|---|---|
839200 | 2016-10-15 14:59:00 | 1125 - Divisible Group Sums | C++ | 0.012 | 1688 |
Accepted
|
839186 | 2016-10-15 14:35:08 | 1125 - Divisible Group Sums | C++ | 0.336 | 1688 |
Accepted
|
没优化前 0.336:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = ;
LL dp[][][]; //dp[i][j][k]表示包含i
int a[N], b[N]; void solve(int n, int m, int d) {
memset(dp, , sizeof(dp));
for(int i = ; i <= n; ++i) {
dp[i][b[i]][] = ;
for(int j = ; j < i; ++j) {
for(int x = ; x < d; ++x) {
for(int y = ; y <= m; ++y) {
dp[i][(b[i] + x) % d][y] += dp[j][x][y - ];
}
}
}
}
} int main()
{
int t, n, q;
scanf("%d", &t);
for(int ca = ; ca <= t; ++ca) {
scanf("%d %d", &n, &q);
for(int i = ; i <= n; ++i) {
scanf("%d", a + i);
}
printf("Case %d:\n", ca);
while(q--) {
int d, m;
scanf("%d %d", &d, &m);
for(int i = ; i <= n; ++i) {
b[i] = (a[i] % d + d) % d;
}
solve(n, m, d);
LL ans = ;
for(int i = ; i <= n; ++i) {
ans += dp[i][][m];
}
printf("%lld\n", ans);
}
}
return ;
}
优化后 0.012:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = ;
LL dp[][][]; //dp[i][j][k]表示前i个
int a[N], b[N]; void solve(int n, int m, int d) {
memset(dp, , sizeof(dp));
for(int i = ; i <= n; ++i) {
dp[i][b[i]][] = ;
for(int j = ; j < d; ++j) {
for(int x = ; x <= m; ++x) {
dp[i][(b[i] + j) % d][x] += dp[i - ][j][x - ];
dp[i][j][x] += dp[i - ][j][x];
}
}
}
} int main()
{
int t, n, q;
scanf("%d", &t);
for(int ca = ; ca <= t; ++ca) {
scanf("%d %d", &n, &q);
for(int i = ; i <= n; ++i) {
scanf("%d", a + i);
}
printf("Case %d:\n", ca);
while(q--) {
int d, m;
scanf("%d %d", &d, &m);
for(int i = ; i <= n; ++i) {
b[i] = (a[i] % d + d) % d;
}
solve(n, m, d);
printf("%lld\n", dp[n][][m]);
}
}
return ;
}
最新文章
- C++中利用数组对字符进行除重和排序
- linux基础-第八单元 正文处理命令及tar命令
- bootstrap tooltip 显示提示信息
- laravel 外键schema RBAC
- Spring表达式语言 之 5.3 SpEL语法(拾肆)
- zencart用chrome无法登录后台
- Leaflet交流
- http方法
- POJ-2386(深广搜基础)
- 基于注解的Spring MVC
- zyUpload界面绝佳、体验超棒的HTML5上传插件
- Linux下gsoap实现webservice功能
- jQuery图片轮播的具体实现
- Java课程设计 学生基本信息管理系统 团队博客
- web全栈应用【爬取(scrapy)数据 ->; 通过restful接口存入数据库 ->; websocket推送展示到前台】
- String对象常量池特性对synchronized对象的影响
- VMware5.5-VMware补丁程序VUM
- 重读redis设计与实现
- ueditor富文本框图片显示
- 用好SVN与Git,版本管理都不是问题
热门文章
- Django admin模块使用search时报错:django.core.exceptions.FieldError: Related Field got invalid lookup: contains
- C 语言 习题 1-12
- python字符串内置用法,择选重要
- 聊聊、Java 命令 第三篇
- python技巧:拆分多层嵌套列表
- CodeForces Round #521 (Div.3) A. Frog Jumping
- KM算法【带权二分图完美匹配】
- Codeforces Round #363 (Div. 2) B 暴力
- iOS-Cocoapods更新不及时
- PowerDesigner反向生成数据库模型(MySql篇)