编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China 头条阅读 学淘股 China Travel
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> 一些DP杂题 -> 正文阅读

[C++]一些DP杂题

1.
[HNOI2001] 产品加工
一道简单的背包,然而我还是写了很久QAQ  
时间范围是都小于5 显然考虑一维背包,dp[i]表示目前A消耗了i的最小B消耗
注意
 if(b[i]) dp[j]=dp[j]+b[i];
 else dp[j]=1e9+7;
可以用B则直接转移,否则要把上一次的这个状态设为正无穷,只能用后两个转移。




//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=6000+299;
const int N=5*6000+9;
int n,a[maxn],b[maxn],c[maxn],dp[N],lz[N],ans=1e9+7; 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    memset(dp,127,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=i*5;j>=0;j--){
            if(b[i]) dp[j]=dp[j]+b[i];
            else dp[j]=1e9+7;//!!!!!!!!!!!!!!!!!!!!
            if(a[i]&&j>=a[i]&&dp[j]>dp[j-a[i]]) dp[j]=dp[j-a[i]];
            if(c[i]&&j>=c[i]&&dp[j]>dp[j-c[i]]+c[i]) dp[j]=dp[j-c[i]]+c[i];
            if(i==n) ans=min(max(dp[j],j),ans);
        }
    cout<<ans;
    return 0;
}

View Code
2.
[HAOI2007]上升序列
看数据范围似乎是n^2可以过的,然而自己之前并不会写nlongn求最长上升子序列的算法就自己YY了一下,写得很丑,单调栈里从短到长从大到小,用了两个二分,一次找找最长的比它小的,一次找长度为它的位置是否可以更新。
这样找到以每个元素打头的最长上升序列,询问就从1到n跑一遍问它能不能到那么长,就保证了字典序最小。




//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
const int maxn=10000+299;
int now,n,m,x,maxx,a[maxn],pre[maxn],dp[maxn],sta[maxn],sl=1,sr;
int ef(int l,int r,int x){
    int res=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[sta[mid]]>x) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
void ef2(int l,int r,int len,int x){
    while(l<=r){
        int mid=(l+r)>>1;
        if(dp[sta[mid]]==len) { if(a[sta[mid]]<=a[x]) sta[mid]=x; break;}
        if(dp[sta[mid]]<len) l=mid+1;
        else if(dp[sta[mid]]>len) r=mid-1;  
    }
}
void work() { 
    for(int i=n;i>=1;i--) {
        dp[i]=1;
        if(sl<=sr) {
        now=ef(sl,sr,a[i]);
        if(now!=-1)
            dp[i]=dp[sta[now]]+1;
        }
        maxx=max(maxx,dp[i]);
        while(sr>=sl&&dp[sta[sr]]<=dp[i]&&a[sta[sr]]<=a[i]) {
            sr--;
        }
        if(sr<sl||dp[sta[sr]]<dp[i]) sta[++sr]=i;
        else ef2(sl,sr,dp[i],i);
    }
}
void query(int x){
    if(x>maxx) puts("Impossible");
    else {
        int pre=0;
        for(int i=1;i<=n;i++) {
            if(dp[i]>=x&&a[i]>pre) {
                pre=a[i];
                if(x==1)
                printf("%d",a[i]);
                else printf("%d ",a[i]);
                x--;
                if(!x) break;
            }
        }
        printf("\n");
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    work();
    scanf("%d",&m);
    for(int i=1;i<=m;i++) {
        scanf("%d",&x);
        query(x); 
    }
    return 0;
}

View Code
然而正确的nlogn求最长上升序列并不是这么写的,只用一个二分,不过在下并不是很清楚,懒得学以后再说吧。
从LLJ大佬那里学到了用线段树的做法,开一颗权值线段树,从后往前把Dp值存进去,每个点找它后面的最大Dp值来更新,感觉和正常的nlogn的思路可能差不多。
3.
UVA - 12063 Zeros and Ones
谷歌翻译神坑,1和0频率相同翻译成0和0频率相同,喵喵喵?
把Case打成case被坑了一波。。对拍才发现QAQ
最好的做法是往后加0或者1 不用特判,不会炸整,往前加的话就要特判,然后注意开 long long ,要模两次保证不会炸 (LLJ大佬说要开usinged long long ,因为 long long 只到2^64-1,实际这题只到2^63所以不用)




//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef unsigned long long LL;
const int maxn=100;
const int maxk=105;
int T,n,k;
LL dp[maxn][maxn][maxk],ans,ll=1; 
void work(){
    if(!k||n&1) {printf("0\n"); return;}
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++) 
            for(int l=0;l<k;l++) {
               if(j) dp[i][j][(l+((ll=1)<<(i-1))%k)%k]+=dp[i-1][j-1][l];
               if(i!=n) dp[i][j][l]+=dp[i-1][j][l];
            }
    ans=0;
    printf("%llu\n",dp[n][n/2][0]);
}
int main()
{

    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        scanf("%d%d",&n,&k);
        printf("Case %d: ",i);
        work(); 
    }
    return 0;
}

View Code
这是往后加的版本

    for(int i=1;i<n;i++)
        for(int j=0;j<=i;j++) 
            for(int l=0;l<k;l++) {
               dp[i+1][j+1][((l<<1)|1)%k]+=dp[i][j][l];
               dp[i+1][j][(l<<1)%k]+=dp[i][j][l];
            }

4.
UVA - 1628 Pizza Delivery
我爱记忆化搜索,记忆化搜索最强。
dp[i][j][o][k]表示i到j的订单已处理好,现在在i或者j 还要送k家的最优解
枚举,记忆化

for(int i=1;i<l;i++) u=max(u,dfs(i,r,0,k-1)+e[i]-k*abs(p[i]-p[o==0?l:r]));
    for(int i=n;i>r;i--) u=max(u,dfs(l,i,1,k-1)+e[i]-k*abs(p[i]-p[o==0?l:r]));

注意这一段先搜两边再中间,可以达到记忆化效果
代码




//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=100+5;
int T,now,dp[maxn][maxn][2][maxn],vis[maxn][maxn][2][maxn],n,p[maxn],e[maxn],ans;
int dfs(int l,int r,int o,int k) {
    if(k==0) return 0;
    if(vis[l][r][o][k]==now) return dp[l][r][o][k];
    vis[l][r][o][k]=now;
    int &u=dp[l][r][o][k];
    u=0;
    for(int i=1;i<l;i++) u=max(u,dfs(i,r,0,k-1)+e[i]-k*abs(p[i]-p[o==0?l:r]));
    for(int i=n;i>r;i--) u=max(u,dfs(l,i,1,k-1)+e[i]-k*abs(p[i]-p[o==0?l:r]));
    return u;  
}
int main()
{
    scanf("%d",&T);
    for(now=1;now<=T;now++) {
    ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=1;i<=n;i++) scanf("%d",&e[i]);
    for(int kk=1;kk<=n;kk++) 
        for(int i=1;i<=n;i++)
        ans=max(ans,dfs(i,i,0,kk-1)+e[i]-kk*abs(p[i]));
    printf("%d\n",ans); 
    }
    return 0;
}

View Code
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章           查看所有文章
加:2017-09-03 23:23:13  更:2017-09-03 23:23:18 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 三丰软件 开发 中国文化 阅读网 头条阅读 学淘股 China Travel 日历 万年历 2020年5日历
2020-5-31 4:53:48
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识