| 题目名称 | 1590. [USACO Feb14] 奶牛的十项全能 |
|---|---|
| 输入输出 | deca.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2014-04-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：47， 提交：60， 通过率：78.33% | ||||
 烟雨 |
100 | 0.590 s | 3.02 MiB | C++ |
 APWTMECRD |
100 | 0.593 s | 3.02 MiB | C++ |
 胡嘉兴 |
100 | 0.624 s | 5.82 MiB | C++ |
 サイタマ |
100 | 0.649 s | 5.82 MiB | C++ |
 AAAAAAAAAA |
100 | 0.662 s | 3.02 MiB | C++ |
 OI永别 |
100 | 0.675 s | 8.32 MiB | C++ |
 ww944606393 |
100 | 0.681 s | 4.32 MiB | C++ |
 cstdio |
100 | 0.687 s | 4.32 MiB | C++ |
|
胡嘉兴 |
100 | 0.721 s | 8.32 MiB | C++ |
|
胡嘉兴 |
100 | 0.721 s | 8.32 MiB | C++ |
| 本题关联比赛 | |||
| 20140414 | |||
| 关于 奶牛的十项全能 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
用不对的复杂度卡过……
虽然这个剪枝很套路但是我太垃圾所以没写 然后居然过了…… | ||||
 Chenyao2333
2014-04-16 11:05
7楼
| ||||
|
回复 @Chenyao :
算法合集中周伟《状态压缩》附带的标程写的很漂亮，可以参考一下 | ||||
|
Chenyao2333
2014-04-14 13:45
5楼
| ||||
|
回复 @Chenyao :
是 | ||||
|
@cstdio 是我代码写搓了么....看你程序的内存和时间不像是状压DP,求教
| ||||
|
@cstdio 状态压缩dp?求看代码,感觉过不去
Chenyao2333
2014-04-14 12:03
2楼
| ||||
|
Orz求解释
 FF_Sky||幻
2014-04-14 11:46
1楼
| ||||
Rapiz
【题目描述】
农夫约翰的奶牛（1≤n≤20），总是方便的标记为1……N，或许应该叫N项全能，因为有N个不同的事件（通常有10个事件）。
牛i有一个s_ij的技能水平（1<=s_ij＜＝1000），是牛i在参与项目j时会得到的分数。每头奶牛必须且只能参加一个项目，每个事件必须有一些牛参加。
所有奶牛总得分为他们参加项目事件中的技能水平和。然而，项目的裁判如果有深刻印象，可以给出奖励分。评委可以给出B种奖励分（1≤B≤20）。奖励分i有三部分：如果奶牛在前k_i事件（包括这些事件其他牛的分数）获得了至少p_i（1< = p_i＜＝40000）分，他们将获得额外的a_i（1<=a_i<=1000）分（前k项触发的奖励积分不算到前k项的分数和，但算到之后的分数和中）。
例如，让我们考虑n = 3头牛技能水平如下：
| cow | ||||
| event | 1 | 2 | 3 | |
| 1 | 5 | 1 | 7 | |
| 2 | 2 | 2 | 4 | |
| 3 | 4 | 2 | 1 | |
【输入格式】
第1行为N和B；
接下来有B行（2--B+1），其中第i+1行为 K_i, P_i,A_i；
再接下来有N行（B+2--B+1+N），其中第B+N+j行表示 s_j1...s_jN. 。
【输出格式】
输出只有一行，即牛得到的最大分数，包括奖励分。
【样例输入】
3 1 2 7 6 5 1 7 2 2 4 4 2 1
【样例输出】
17
【提示】
输出解释：
牛1参与项目1，牛2参与项目3，牛3参与项目2。
【来源】
USACO Feb14