HDU 5800 To My Girlfriend(单调DP)

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=5800

【题目大意】

  给出一个容量上限s,f[i][j][k][l][m]表示k和l两个物品不能选,i和j两个物品必选,最终质量为m的方案数。求这些方案数的总和。

【题解】

  令dp[i][j][s1][s2]表示前i个物品填了j的体积,有s1个物品选为为必选,s2个物品选为必不选的方案数(0<=s1,s2<=2),则有转移方程dp[i][j][s1][s2]=dp[i-1][j][s1][s2]+dp[i-1][j-a[i]][s1-1][s2]+dp[i-1][j][s1][s2-1],边界条件为dp[0][0][0][0]=1,时间复杂度O(NS*3^2)。

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long LL;
const int N=1005;
const LL mod=1e9+7;
int a[N],n,s,t,T;
LL dp[2][N][3][3],ans;
void add(LL &a,LL b){a=a+b;if(a>mod)a-=mod;}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&s);
        rep(i,n)scanf("%d",a+i);
        memset(dp,t=0,sizeof(dp));
        dp[0][0][0][0]=1;ans=0;
        rep(i,n){
            t^=1;
            for(int j=s;j>=0;j--){
                for(int u=0;u<3;u++)for(int v=0;v<3;v++){
                    dp[t][j][u][v]=dp[t^1][j][u][v];
                    if(j>=a[i])add(dp[t][j][u][v],dp[t^1][j-a[i]][u][v]);
                    if(u&&j>=a[i])add(dp[t][j][u][v],dp[t^1][j-a[i]][u-1][v]);
                    if(v)add(dp[t][j][u][v],dp[t^1][j][u][v-1]);
                }
            }
        }rep(i,s)add(ans,dp[t][i][2][2]);
        ans=((ans*2)%mod)*2%mod;
        printf("%lld\n",ans);
    }return 0;
}

  

时间: 11-16

HDU 5800 To My Girlfriend(单调DP)的相关文章

hdu 5800 To My Girlfriend + dp

传送门:hdu 5800 To My Girlfriend 题意:给定n个物品,其中i,j必选,l,m必不选,问组成体积为s的方法一共有多少种 思路:定义dp[i][j][s1][s2],表示前i种物品能够构成的体积为j,其中有s1种定为必选,s2种定为不必选;因为递推到第i层时,只与第i-1层有关,所以把第一维降到2来省内存.然后就是dp[i][j][s1][s2]=dp[i-1][j][s1][s2]+dp[i-1][j][s1][s2-1]+dp[i-1][j-a[i]][s1-1][s2

HDU 5800 To My Girlfriend (动态规划)

题目链接:HDU 5800 题面: To My Girlfriend Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 737    Accepted Submission(s): 292 Problem Description Dear Guo I never forget the moment I met with you.You c

HDU 5800 To My Girlfriend

题目:To My Girlfriend 链接:http://acm.hdu.edu.cn/showproblem.php?pid=5800 题意: 给你n.s,接下来n个数,定义 f ( i , j , k , l , m )表示下标为i.j的必选,k.l的必不选,且和为m的 子集 数量. 然后求上图式子的值. 思路: 刚开始想着i 个数的和小于等于s 的子集数量,定义了dp[i][j]表示i 个数,和为j 的情况数量,不管怎么优化死活要n^3级别.看了题解,才觉醒... 定义dp[i][j][

HDU 5800 (DP)

Problem To My Girlfriend (HDU 5800) 题目大意 给定一个由n个元素组成的序列,和s (n<=1000,s<=1000) 求 :   f (i,j,k,l,m) 指必定选第i,j号元素,必定不选k,l号元素,选的元素总和为m的子集个数. 解题分析 一开始想了个n^3的DP,f[j][k]表示选j个数总和为k的方案数,然后一直想着怎么去优化,陷进死胡同,到比赛结束还没想出来. 看了题解后,感觉智商被藐视了. 题解的做法是f[i][j][s1][s2]表示前i个数总

hdu 3217 Health(状态压缩DP)

Health Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 527    Accepted Submission(s): 145 Problem Description Unfortunately YY gets ill, but he does not want to go to hospital. His girlfriend LM

hdu 1207 汉诺塔II (DP+递推)

汉诺塔II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4529    Accepted Submission(s): 2231 Problem Description 经典的汉诺塔问题经常作为一个递归的经典例题存在.可能有人并不知道汉诺塔问题的典故.汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往

HDU 1024 Max Sum Plus Plus --- dp+滚动数组

HDU 1024 题目大意:给定m和n以及n个数,求n个数的m个连续子系列的最大值,要求子序列不想交. 解题思路:<1>动态规划,定义状态dp[i][j]表示序列前j个数的i段子序列的值,其中第i个子序列包括a[j], 则max(dp[m][k]),m<=k<=n 即为所求的结果 <2>初始状态: dp[i][0] = 0, dp[0][j] = 0; <3>状态转移: 决策:a[j]自己成为一个子段,还是接在前面一个子段的后面 方程: a[j]直接接在前面

hdu 5623 KK&#39;s Number(dp)

问题描述 我们可爱的KK有一个有趣的数学游戏:这个游戏需要两个人,有N\left(1\leq N\leq 5*{10}^{4} \right)N(1≤N≤5∗10?4??)个数,每次KK都会先拿数.每次可以拿任意多个数,直到NN个数被拿完.每次获得的得分为取的数中的最小值,KK和对手的策略都是尽可能使得自己的得分减去对手的得分更大.在这样的情况下,最终KK的得分减去对手的得分会是多少? 输入描述 第一行一个数T\left( 1\leq T\leq 10\right)T(1≤T≤10),表示数据组

hdu 2147 kiki&#39;s game(DP(SG)打表找规律)

题意: n*m的棋盘,一枚硬币右上角,每人每次可将硬币移向三个方向之一(一格单位):左边,下边,左下边. 无法移动硬币的人负. 给出n和m,问,先手胜还是后手胜. 数据范围: n, m (0<n,m<=2000) 思路: dp[i][j]=0,说明从(i,j)这个点到时左下角先手败.dp[i][j]=1则先手胜. 然后记忆搜.但是记忆搜会超时. 搜完把整张表打出来,发现规律了,,,,然后,,,代码剩几行了. 代码: ///打表观察 /* int f[2005][2005]; int go(in