Codeforces Round #160 (Div. 2) D. Maxim and Restaurant(DP)

时间:2022-12-28 13:10:54

题目链接

想了挺久,枚举每一件物品,当做关键物品,假设再加这一件物品,就>=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)的更多相关文章

  1. Codeforces Round &num;160 &lpar;Div&period; 1&rpar; 题解【ABCD】

    Codeforces Round #160 (Div. 1) A - Maxim and Discounts 题意 给你n个折扣,m个物品,每个折扣都可以使用无限次,每次你使用第i个折扣的时候,你必须 ...

  2. Codeforces Round &num;622 &lpar;Div&period; 2&rpar; A&period; Fast Food Restaurant(全排列,DFS)

    Codeforces Round #622 (Div. 2) A. Fast Food Restaurant 题意: 你是餐馆老板,虽然只会做三道菜,上菜时还有个怪癖:一位客人至少上一道菜,且一种菜最 ...

  3. Codeforces Round &num;367 &lpar;Div&period; 2&rpar; C&period; Hard problem(DP)

    Hard problem 题目链接: http://codeforces.com/contest/706/problem/C Description Vasiliy is fond of solvin ...

  4. Codeforces Round &num;160 &lpar;Div&period; 2&rpar;

    A. Roma and Lucky Numbers 暴力计算. B. Roma and Changing Signs 每次取最小值改变正负,优先队列维护. C. Maxim and Discounts ...

  5. Codeforces Round &num;374 &lpar;Div&period; 2&rpar; D&period; Maxim and Array 贪心

    D. Maxim and Array 题目连接: http://codeforces.com/contest/721/problem/D Description Recently Maxim has ...

  6. Codeforces Round &num;374 &lpar;Div&period; 2&rpar; D&period; Maxim and Array —— 贪心

    题目链接:http://codeforces.com/problemset/problem/721/D D. Maxim and Array time limit per test 2 seconds ...

  7. Codeforces Round &num;374 &lpar;Div&period; 2&rpar; D&period; Maxim and Array 线段树&plus;贪心

    D. Maxim and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

  8. Codeforces Round &num;374 &lpar;Div&period; 2&rpar; D&period; Maxim and Array

    传送门 分析:其实没什么好分析的.统计一下负数个数.如果负数个数是偶数的话,就要尽量增加负数或者减少负数.是奇数的话就努力增大每个数的绝对值.用一个优先队列搞一下就行了. 我感觉这道题的细节极为多,非 ...

  9. Codeforces Round &num;160 &lpar;Div&period; 2&rpar;---A&period; Roma and Lucky Numbers

    Roma and Lucky Numbers time limit per test 1 second memory limit per test 256 megabytes input standa ...

随机推荐

  1. laravel 事件的使用案例

    以下是我对事件使用的一些记录 创建事件 执行以下命令,执行完成后,会在 app\Events 下面出现一个 DeleteEvent.php 文件,事件就在次定义 php artisan make:ev ...

  2. SQL语句转摘

    http://www.cnblogs.com/Olive116/p/3271706.html 收藏没有用,来收到留链接

  3. 动态规划之LCS&lpar;最大公共子序列&rpar;

    #include <stdio.h> #include <string.h> int b[50][50]; int c[50][50]; int length = 0; voi ...

  4. VS2012 编译 Assimp

    VS2012 编译 Assimp 环境: assimp-3.1.1Windows 7 64BitVisual Studio 2012CMake 2.8.12.1 注意: 在Windows中编译assi ...

  5. 编写更好的CSS

    编写好的CSS代码能提升页面的渲染速度.本质上,一条规则都没有引擎解析的最快.MDN上将CSS选择符归拆分成四个主要类别,如下所示,性能依次降低. ID 规则 Class 规则 标签规则 通用规则 对 ...

  6. 使用Boostrap框架写一个登录&bsol;注册界面

    Bootstrap是一个Web前端开发框架,使用它提供的css.js文件可以简单.方便地美化HTML控件.一般情况下,对控件的美化需要我们自己编写css代码,并通过标签选择器.类选择器.ID选择器为指 ...

  7. Day032--Python--操作系统&comma; process进程

    多道技术背景: 提高工作效率(充分利用I/O阻塞的时间)    (I: input, O: output) 同时执行多个任务 多道技术: 空间复用: 充分利用内存空间 时间复用: 充分利用I/O阻塞时 ...

  8. windows加固

    1. 账户管理和认证授权 1.1 账户 默认账户安全 禁用Guest账户. 禁用或删除其他无用账户(建议先禁用账户三个月,待确认没有问题后删除.) 操作步骤 打开 控制面板 > 管理工具 &gt ...

  9. 浪潮IOT知识点

    1 新增身份定义 以及 身份定义的属性表 要注意增加路由 2     '@trident/core'; 飘红,解决办法 import { TableSearchComponent } from '@t ...

  10. k-SLAM:k-mer Sorted List Alignment and Metagenomics

    k-SLAM 是基于大量高通量宏基因组序列数据分析的比对程序,它基于k-mer技术上在reads和序列之间进行比较,然后用Smith-Waterman算法验证.校准是连接在一起组成一个伪组装用来提高特 ...