想了挺久,枚举每一件物品,当做关键物品,假设再加这一件物品,就>=c了,把剩下的物品背一下包,dp[i][j]表示i个物品可以组成重量j的个数。
这样就可以知道前面放i件,后边肯定放n-i-1件,乱搞搞,算double,边乘边算保证不要越界。最后注意,LL和sum <= c的时候情况。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL __int64
LL dp[][][];
int p[];
int main()
{
int i,j,k,u,v,n,c,s1,s2,sum;
double ans = ;
scanf("%d",&n);
sum = ;
for(i = ; i <= n; i ++)
{
scanf("%d",&p[i]);
sum += p[i];
}
scanf("%d",&c);
if(sum <= c)
{
printf("%d\n",n);
return ;
}
for(i = ; i <= n; i ++)
{
memset(dp,,sizeof(dp));
dp[][][] = ;
s1 = ;
s2 = ;
for(j = ; j <= n; j ++)
{
if(i == j) continue;
for(k = ; k < j; k ++)
{
for(u = ; u <= ; u ++)
dp[s2][k][u] = dp[s1][k][u];
}
for(k = ; k < j; k ++)
{
for(u = ; u < ; u ++)
{
if(dp[s1][k][u])
{
if(u+p[j] <= )
dp[s2][k+][u+p[j]] += dp[s1][k][u];
}
}
}
swap(s1,s2);
}
for(j = ; j < c; j ++)
{
if(j + p[i] >= c)
{
for(k = ; k < n; k ++)
{
if(dp[s1][k][j] == ) continue;
double temp = dp[s1][k][j];
for(u = ,v = k+;u <= n-k-;u ++,v++)
temp *= u*1.0/v;
temp /= n;
if(j + p[i] == c)
ans += temp*(k+);
else
ans += temp*k;
}
}
}
}
printf("%lf\n",ans);
return ;
}
Codeforces Round #160 (Div. 2) D. Maxim and Restaurant(DP)的更多相关文章
-
Codeforces Round #160 (Div. 1) 题解【ABCD】
Codeforces Round #160 (Div. 1) A - Maxim and Discounts 题意 给你n个折扣,m个物品,每个折扣都可以使用无限次,每次你使用第i个折扣的时候,你必须 ...
-
Codeforces Round #622 (Div. 2) A. Fast Food Restaurant(全排列,DFS)
Codeforces Round #622 (Div. 2) A. Fast Food Restaurant 题意: 你是餐馆老板,虽然只会做三道菜,上菜时还有个怪癖:一位客人至少上一道菜,且一种菜最 ...
-
Codeforces Round #367 (Div. 2) C. Hard problem(DP)
Hard problem 题目链接: http://codeforces.com/contest/706/problem/C Description Vasiliy is fond of solvin ...
-
Codeforces Round #160 (Div. 2)
A. Roma and Lucky Numbers 暴力计算. B. Roma and Changing Signs 每次取最小值改变正负,优先队列维护. C. Maxim and Discounts ...
-
Codeforces Round #374 (Div. 2) D. Maxim and Array 贪心
D. Maxim and Array 题目连接: http://codeforces.com/contest/721/problem/D Description Recently Maxim has ...
-
Codeforces Round #374 (Div. 2) D. Maxim and Array —— 贪心
题目链接:http://codeforces.com/problemset/problem/721/D D. Maxim and Array time limit per test 2 seconds ...
-
Codeforces Round #374 (Div. 2) D. Maxim and Array 线段树+贪心
D. Maxim and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
Codeforces Round #374 (Div. 2) D. Maxim and Array
传送门 分析:其实没什么好分析的.统计一下负数个数.如果负数个数是偶数的话,就要尽量增加负数或者减少负数.是奇数的话就努力增大每个数的绝对值.用一个优先队列搞一下就行了. 我感觉这道题的细节极为多,非 ...
-
Codeforces Round #160 (Div. 2)---A. Roma and Lucky Numbers
Roma and Lucky Numbers time limit per test 1 second memory limit per test 256 megabytes input standa ...
随机推荐
-
laravel 事件的使用案例
以下是我对事件使用的一些记录 创建事件 执行以下命令,执行完成后,会在 app\Events 下面出现一个 DeleteEvent.php 文件,事件就在次定义 php artisan make:ev ...
-
SQL语句转摘
http://www.cnblogs.com/Olive116/p/3271706.html 收藏没有用,来收到留链接
-
动态规划之LCS(最大公共子序列)
#include <stdio.h> #include <string.h> int b[50][50]; int c[50][50]; int length = 0; voi ...
-
VS2012 编译 Assimp
VS2012 编译 Assimp 环境: assimp-3.1.1Windows 7 64BitVisual Studio 2012CMake 2.8.12.1 注意: 在Windows中编译assi ...
-
编写更好的CSS
编写好的CSS代码能提升页面的渲染速度.本质上,一条规则都没有引擎解析的最快.MDN上将CSS选择符归拆分成四个主要类别,如下所示,性能依次降低. ID 规则 Class 规则 标签规则 通用规则 对 ...
-
使用Boostrap框架写一个登录\注册界面
Bootstrap是一个Web前端开发框架,使用它提供的css.js文件可以简单.方便地美化HTML控件.一般情况下,对控件的美化需要我们自己编写css代码,并通过标签选择器.类选择器.ID选择器为指 ...
-
Day032--Python--操作系统, process进程
多道技术背景: 提高工作效率(充分利用I/O阻塞的时间) (I: input, O: output) 同时执行多个任务 多道技术: 空间复用: 充分利用内存空间 时间复用: 充分利用I/O阻塞时 ...
-
windows加固
1. 账户管理和认证授权 1.1 账户 默认账户安全 禁用Guest账户. 禁用或删除其他无用账户(建议先禁用账户三个月,待确认没有问题后删除.) 操作步骤 打开 控制面板 > 管理工具 > ...
-
浪潮IOT知识点
1 新增身份定义 以及 身份定义的属性表 要注意增加路由 2 '@trident/core'; 飘红,解决办法 import { TableSearchComponent } from '@t ...
-
k-SLAM:k-mer Sorted List Alignment and Metagenomics
k-SLAM 是基于大量高通量宏基因组序列数据分析的比对程序,它基于k-mer技术上在reads和序列之间进行比较,然后用Smith-Waterman算法验证.校准是连接在一起组成一个伪组装用来提高特 ...