从入门到模板

从入门到模板

POJ 3186 Treats for the Cows

一初始想到的是,用三个注解位记录取第i个数的时刻,但后来意识那几个主意十分,可能性太多,无法推

然后就看了然题报告的思路,说是用区间dp,状态是设出来了,但受固有考虑影响,老想着怎么顺着推。

末段实际上想不出了,看了代码,才意识要逆着推,从停止状态开头推起,那样公式就出来了

为了确认保障每风流罗曼蒂克层循环要用到的值都已被总结出来了,按间距长度实行枚举

怀恋第一个区间dp吧

 

/*
dp[i][j]:剩下第i个至第j个物品时,取掉剩下的所有物品能获得的最大值 
dp[i][j]=max(dp[i+1][j]+v[i]*(n-(j-i+1)+1),dp[i][j-1]+v[j]*(n-(j-i+1)+1));
*/
#include
#include
#include
using namespace std;
int n,v[2005],dp[2005][2005];
void init(){
 //memset(dp,-1,sizeof(dp));
 for(int i=1;i<=n;i++) dp[i][i]=v[i]*n;
}
int main(){
 #ifndef ONLINE_JUDGE
 freopen("in.txt","r",stdin);
 #endif
 scanf("%d",&n);
 for(int i=1;i<=n;i++) scanf("%d",&v[i]);
 int tmp;
 init();
 int j;
 for(int l=2;l<=n;l++){//逆着推,从最后出队列的开始推起,按区间长度枚举
  for(int i=1;i<=n;i++){
   j=i+l-1;
   dp[i][j]=max(dp[i+1][j]+v[i]*(n-(l-1)),dp[i][j-1]+v[j]*(n-(l-1)));
  }
 }
 printf("%d\n",dp[1][n]);
}

 

3186 Treats for the Cows
一早前想到的是,用二个标记位记录取第i个数的时光,但后来发觉这些措施丰盛,恐怕性太多,不能推
然后就看了…

43

 

#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<string>  

using namespace std;  

typedef long long ll;  

ll dp[20][163][163][2];  
int a[20];  
ll dfs(int pos,int sum,int val,int mod,bool limit)  
{  
    if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac  
    if(pos==-1) return sum==0 && val==0;  
    if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];  
    int up=limit?a[pos]:9;  
    ll ans=0;  
    for(int i=0;i<=up;i++)  
    {  
        if(sum-i<0) break;  
        ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]);  
    }  
    dp[pos][sum][val][limit]=ans;  
    return ans;  
}  
ll solve(ll x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    ll ans=0;  
    for(int i=1;i<=pos*9;i++)//上限就是每一位都是9  
    {  
        memset(dp,-1,sizeof dp);  
        ll tmp=dfs(pos-1,i,0,i,true);  
        ans+=tmp;  
    }  
    return ans;  
}  
int main()  
{  
//    cout<<18*9<<endl;  
    ll le,ri;  
//    memset(dp,-1,sizeof dp);  
    while(~scanf("%lld%lld",&le,&ri))  
        printf("%lld\n",solve(ri)-solve(le-1));  
    return 0;  
}  
/* 
1 1000000000000000000 
*/  

Hint

w_w
是吧!统计[1,ri]数量和[1,le-1],然后相减就是间距[le,ri]的数目了,这里小编写的下界是1,其实0也行,反正相减后就没了,注意标题中le的范围都以过量等于1的(不然le=0,再减风流倜傥就G_G了)
在讲例题在此以前先讲个着力的动态模板(先看前面包车型客车例题也行):dp思想,枚举到当下职分pos,状态为state(那些便是依据标题来的,恐怕相当多,毕竟dp风云万变)的数据(既然是计数,dp值鲜明是保存满意条件数的个数)

Source

  • … + A2
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6568   Accepted: 3459
int main()  
{  
    long long le,ri;  
    while(~scanf("%lld%lld",&le,&ri))  
        printf("%lld\n",solve(ri)-solve(le-1));  
}  

 


Line 1: The maximum
revenue FJ can achieve by selling the treats

#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<string>  

using namespace std;  
const int N=1e4+5;  
int dp[12][N];  
int f(int x)  
{  
    if(x==0) return 0;  
    int ans=f(x/10);  
    return ans*2+(x%10);  
}  
int all;  
int a[12];  
int dfs(int pos,int sum,bool limit)  
{  
    if(pos==-1) {return sum<=all;}  
    if(sum>all) return 0;  
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];  
    int up=limit ? a[pos] : 9;  
    int ans=0;  
    for(int i=0;i<=up;i++)  
    {  
        ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);  
    }  
    if(!limit) dp[pos][all-sum]=ans;  
    return ans;  
}  
int solve(int x)  
{  
    int pos=0;  
    while(x)  
    {  
        a[pos++]=x%10;  
        x/=10;  
    }  
    return dfs(pos-1,0,true);  
}  
int main()  
{  
    int a,ri;  
    int T_T;  
    int kase=1;  
    scanf("%d",&T_T);  
    memset(dp,-1,sizeof dp);  
    while(T_T--)  
    {  
        scanf("%d%d",&a,&ri);  
        all=f(a);  
        printf("Case #%d: %d\n",kase++,solve(ri));  
    }  
    return 0;  
}  
 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 2e3 + 10  ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int dp[maxn][maxn], a[maxn], n;
25 int main(){
26     // freopen("in.txt","r",stdin);
27     // freopen("out.txt","w",stdout);
28     while(~scanf("%d",&n)){
29         for(int i=1;i<=n;i++){
30             scanf("%d",&a[i]);
31             dp[i][0]=a[i]*n;
32         }
33         for(int j=1;j<n;j++)
34             for(int i=n-j;i>0;i--)
35                 dp[i][j]=max(dp[i][j-1]+a[i+j]*(n-j),dp[i+1][j-1]+a[i]*(n-j));
36         printf("%d\n",dp[1][n-1]);
37     }
38     return 0;
39 }

新的小圈子–计数转求和
HDU
4507
那题麻烦正是需要数的平方和。
我们先思探讨和的难题,叁个间隔,数位dp能在局地封锁下计数,今后要那几个数的和。其实组合数学搞搞就能够了:如
今后枚举的某壹位pos,小编总结了那一人枚举i的知足条件的个数cnt,其实假如算i对总和的进献就足以了,对于三个数来说第pos位是i,那么对求和孝敬正是i10^pos,就是十进制的权值,然后有cnt个数都满意第pos位是i,末了sum=cnti10^pos.原理正是那样平方和能够看做(a10pos+b)2,a是您日前pos位要枚举的,b其实是个头难点,就是pos之后的位的贡献值,把那些平方展开就足以了!

  • The treats are
    numbered 1..N and stored sequentially in single file in a long box
    that is open at both ends. On any day, FJ can retrieve one treat
    from either end of his stash of treats.
  • Like fine wines and
    delicious cheeses, the treats improve with age and command greater
    prices.
  • The treats are not
    uniform: some are better and have higher intrinsic value. Treat i
    has value v(i) (1 <= v(i) <= 1000).
  • Cows pay more for
    treats that have aged longer: a cow will pay v(i)*a for a treat of
    age a.

    Given the values v(i) of
    each of the treats lined up in order of the index i in their box, what
    is the greatest value FJ can receive for them if he orders their sale
    optimally? 

入门就没多少讲了,起始讲常用优化吧!
率先:memset(dp,-1,sizeof dp);放在多组数据外面。
那或多或少是二个数位特点,使用的法规是:约束标准是各种数本人的品质,而与输入非亲非故。
现实的:上风度翩翩题不要62和4,这几个节制对每二个数都是鲜明的,正是说任性一个数满不满意这几个限制都以分明,比方444以此数,它不满意限制标准,不管你输入的间隔是不怎么你都没办法儿改正这么些数不满意约束那一个实际,那就是数本人的脾性(大家每组数据只是在间距计数而已,只好说你输入的间隔不含有444的话,大家就不把它总结在内,而无法改动任何实际卡塔尔。
透过,大家保留的景观就足以一贯用(注意还应该有要limit,差异间隔是会影响数位在有约束规范下的上限的)
这一点优化就不给现实难题了,这么些还也许有更加的恢宏。不过说几个自身遭遇的简约的束缚:
1.求数位和是10的翻番的个数,这里简化为数位sum%10以此情况,即dp[pos][sum]此处10
是与多组非亲非故的,所以能够memset优化,可是注意假诺难点的模是输入的话这就无法如此了。
2.求二进制1的数量与0的数量相等的个数,那几个也是数自身的习性。
3.。。。。。
也许做题累积吧。搞懂观念!
上面介绍的点子正是要行memset优化,把不满意前提的经过更动,然后优化。
介绍从前,先说大器晚成种较为愚笨的改革,那正是增添状态,前边讲limit之处说扩张意气风发维dp[pos][state][limit],能把不相同情状下意况分别记录(可是这么些不可能memset放外面)。基于那一个酌量,大家着想:限制为数位是p的倍数的个数,在那之中p数输入的,那和上边sum%10临近,可是dp[pos][sum]明朗已经十三分了,每便p恐怕都不相符,为了强行把memset提到外面加状态dp[pos][sum][p],对于各样不相同p分别保存对应的气象。这里前提就比较容易了,你dp数组必得合法,p太大就G_G了。所以对于与输入有关的自律都足以强行增添状态(这并不意味能ac,如若问题数据少的话就随意你瞎搞了)
第二:相减。
例题:HDU
4734
标题给了个f(x)的定义:F(x) = An

Lines 2..N+1: Line i+1
contains the value of treat v(i)

admin

网站地图xml地图