补补弱项 全面发展。。
从最基础来
sdut1299最长上升子序
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[];
int a[];
int main()
{
int i,j,k,n;
cin>>n;
for(i =; i <= n ; i++)
{
cin>>a[i];
dp[i] = ;
}
for(i = ; i <= n ;i++)
for(j = ; j < i ; j++)
if(a[i]>a[j])
{
dp[i] = max(dp[j]+,dp[i]);
}
int maxz = ;
for(i = ; i <= n ;i++)
maxz = max(dp[i],maxz);
cout<<maxz<<endl;
return ;
} /**************************************
Problem id : SDUT OJ 1299
User name : 尚雨
Result : Accepted
Take Memory : 476K
Take Time : 0MS
Submit Time : 2013-08-05 09:26:48
**************************************/
hdu2084数塔
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][];
int a[][];
int main()
{
int i,j,k,n,t;
cin>>t;
while(t--)
{
cin>>n;
memset(dp,,sizeof(dp));
for(i = ; i <= n ;i++)
for(j = ; j <= i ;j++)
cin>>a[i][j];
for(j = ; j <= n ; j++)
dp[n][j] = a[n][j];
for(i = n- ; i >= ;i--)
for(j = ; j <= i ; j++)
{
dp[i][j]=a[i][j]+max(dp[i+][j],dp[i+][j+]);
}
cout<<dp[][]<<endl;
}
return ;
}
hdu1159最长公共子序列
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][];
char s1[],s2[];
int main()
{
int i,j,k1,k2;
while(cin>>s1)
{
k1 = strlen(s1);
cin>>s2;
k2 = strlen(s2);
memset(dp,,sizeof(dp));
for(i = ; i <= k1 ; i++)
for(j = ; j <= k2 ; j++)
{
if(s1[i-]==s2[j-])
dp[i][j] = dp[i-][j-]+;
else
dp[i][j] = max(dp[i-][j],dp[i][j-]);
}
cout<<dp[k1][k2]<<endl;
}
return ;
}
hdu1003最大子段和
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
int dp[];
int a[];
int main()
{
int i,j,n,t,kk=;
cin>>t;
while(t--)
{
cin>>n;kk++;
for(i = ; i <= n ;i++)
cin>>a[i];
int maxz = -INF,tmaxz=;
int x=,y,tx=;
for(i = ; i <= n ;i++)
{
tmaxz+=a[i];
if(tmaxz>maxz)
{
maxz = tmaxz;
x = tx;
y = i;
}
if(tmaxz<)
{
tmaxz=;
tx = i+;
}
}
printf("Case %d:\n",kk);
cout<<maxz<<" "<<x<<" "<<y<<endl;
if(t!=)
puts("");
}
return ;
}
sdut1225http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1225
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
char s1[],s2[];
int dp[][];
int main()
{
int i,j,k1,k2;
while(cin>>s1)
{
cin>>s2;
memset(dp,,sizeof(dp));
k1 = strlen(s1);
k2 = strlen(s2);
for(i = ; i <= k1 ; i++)
dp[i][] = i;
for(i = ; i <= k2 ; i++)
dp[][i] = i;
for(i = ; i <= k1 ; i++)
for(j = ; j <= k2 ; j++)
{
if(s1[i-]==s2[j-])
dp[i][j] = dp[i-][j-];
else
dp[i][j] = dp[i-][j-]+;
dp[i][j] = min(dp[i][j],min(dp[i-][j]+,dp[i][j-]+));
}
cout<<dp[k1][k2]<<endl;
}
return ;
}
hdu1058 预处理出所有的数 预处理的技巧挺好
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[];
void init()
{
int i,j,a=,b=,c=,d=,ii,jj,g,o;
ii=jj=g=o=;
dp[] = ;
for(i = ; i <= ;i++)
{
int x = dp[ii]*a;
int y = dp[jj]*b;
int z = dp[g]*c;
int w = dp[o]*d;
dp[i] = min(min(x,y),min(z,w));
if(dp[i]==x)
ii++;
if(dp[i]==y)
jj++;
if(dp[i]==z)
g++;
if(dp[i]==w)
o++;
}
}
int main()
{
int i,j,k,n;
init();
while(cin>>n)
{
if(n==)
break;
if(n%==&&n%!=)
printf("The %dst humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %dnd humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %drd humble number is %d.\n",n,dp[n]);
else
printf("The %dth humble number is %d.\n",n,dp[n]);
}
return ;
}
hdu2571 类似数塔
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0xfffffff
using namespace std;
int dp[][];
int v[][];
int main()
{
int i,j,n,m,t,g;
cin>>t;
while(t--)
{
cin>>n>>m;
for(i = ; i <= n ;i++)
for(j = ; j <= m ; j++)
{
cin>>v[i][j];
dp[i][j] = -INF;
}
dp[][] = v[][];
for(i = ;i <= n ;i++)
for(j = ; j <= m ; j++)
{
if(i<n)
dp[i+][j] = max(dp[i][j]+v[i+][j],dp[i+][j]);
if(j<m)
dp[i][j+] = max(dp[i][j]+v[i][j+],dp[i][j+]);
for(g = ;;g++)
{
if(g*j>m)
break;
dp[i][g*j] = max(dp[i][j]+v[i][g*j],dp[i][g*j]);
}
}
cout<<dp[n][m]<<endl;
}
return ;
}
嵌套矩形 类似最长上升子序 因没排序WA了几次
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
struct node
{
int a,b;
}q[];
int dp[];
bool cmp(node a,node b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
int main()
{
int i,j,t,n,tt;
cin>>t;
while(t--)
{
cin>>n;
memset(dp,,sizeof(dp));
for(i = ; i <= n ;i++)
{
cin>>q[i].a>>q[i].b;
if(q[i].a>q[i].b)
{
tt = q[i].a;
q[i].a = q[i].b;
q[i].b = tt;
}
dp[i] = ;
}
sort(q+,q+n+,cmp);
for(i = ; i <= n ; i++)
for(j = ; j < i ; j++)
{
if(((q[i].a>q[j].a)&&(q[i].b>q[j].b))||(q[i].b>q[j].a&&q[i].a>q[j].b))
dp[i] = max(dp[i],dp[j]+);
}
int maxz=;
for(i = ; i <= n ;i++)
maxz = max(maxz,dp[i]);
cout<<maxz<<endl;
}
return ;
}
Vijos 1493 传纸条 多进程DP
四维
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][][][];
int a[][];
int main()
{
int i,j,n,m,g,o;
while(cin>>n>>m)
{
memset(dp,,sizeof(dp));
memset(a,,sizeof(a));
for(i = ; i <= n ; i++)
for(j = ; j <= m ; j++)
scanf("%d",&a[i][j]);
for(i = ; i <= n ;i++)
for(j = ; j <= m ; j++)
for(g = ; g <= n ; g++)
for(o = ;o <= m ;o++)
{
dp[i][j][g][o] = max(max(dp[i-][j][g-][o],dp[i-][j][g][o-]),max(dp[i][j-][g-][o],dp[i][j-][g][o-]));
if(i==g&&j==o)
dp[i][j][g][o]+=a[i][j];
else
dp[i][j][g][o]+=a[i][j]+a[g][o];
}
printf("%d\n",dp[n][m][n][m]);
}
return ;
}
因为它只能从两个方向走过来 很巧妙的可以转换为3维的
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][][];
int a[][],d[][];
int main()
{
int i,j,n,m,g,o,x,y,z,p;
while(cin>>n>>m)
{
memset(dp,,sizeof(dp));
memset(d,,sizeof(d));
for(i = ; i <= n ; i++)
for(j = ; j <= m ; j++)
{
scanf("%d",&a[i][j]);
if(i+j>n)
d[i+j-][n-i+] = a[i][j];
else
d[i+j-][j] = a[i][j];
}
for(i = ; i < n+m ; i++)
for(j = ;j <= m ; j++)
for(g = ; g <= m ;g++)
{
if(i <= n)
{
x = dp[i-][j][g-];
y = dp[i-][j-][g-];
z = dp[i-][j][g];
p = dp[i-][j-][g];
}
else
{
x = dp[i-][j][g];
y = dp[i-][j+][g+];
z = dp[i-][j+][g];
p = dp[i-][j][g+];
}
dp[i][j][g] = max(max(x,y),max(z,p));
if(j==g)
dp[i][j][g]+=d[i][j];
else
dp[i][j][g]+=d[i][j]+d[i][g];
}
cout<<dp[n+m-][][]<<endl; }
return ;
}
hdu1059http://acm.hdu.edu.cn/showproblem.php?pid=1059
多重背包 优化一下 时间卡的很紧
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int a[],b[],d[];
int dp[];
int main()
{
int i,j,k,s=,g,n=,kk=;
while(scanf("%d",&a[])!=EOF)
{
s=;
s+=a[];g=;kk++;
memset(b,,sizeof(b));
for(i = ; i <= ; i++)
{
scanf("%d",&a[i]);
s+=a[i]*i;
n+=a[i];
}
if(s==) break;
printf("Collection #%d:\n",kk);
if(s%!=)
{
printf("Can't be divided.\n\n");
continue;
}
else
s = s/;
d[] = ;
for(i = ; i <= s ; i++)
dp[i] = ;
for(i = ; i < ; i++)
d[i] = d[i-]<<;
j=;
for(i = ; i <= ; i++)
{
k = ;
while(a[i]>d[k])
{
a[i]-=d[k];
b[++j] = d[k]*i;
k++;
}
if(a[i])
{
b[++j] = a[i]*i;
}
}
k = j;
for(i = ; i <= k ; i++)
for(j = s ; j >= b[i] ; j--)
{
dp[j] = max(dp[j-b[i]]+b[i],dp[j]);
}
if(dp[s]==s)
printf("Can be divided.\n");
else
printf("Can't be divided.\n");
puts("");
}
return ;
}
hdu1176免费馅饼 http://acm.hdu.edu.cn/showproblem.php?pid=1176
将每秒的状态合起来类似数塔 倒推回去就行
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][];
int main()
{
int i,j,k,n,x,t;
while(scanf("%d",&n)&&n)
{
memset(dp,,sizeof(dp));
int maxz=;
for(i = ;i <= n ; i++)
{
scanf("%d%d",&x,&t);
dp[t][x+]++;
maxz = max(maxz,t);
}
for(i = maxz- ; i >= ; i--)
for(j = ; j <= ; j++)
{
dp[i][j]+=max(max(dp[i+][j-],dp[i+][j+]),dp[i+][j]);
}
cout<<dp[][]<<endl;
}
return ;
}
hdu1069http://acm.hdu.edu.cn/showproblem.php?pid=1069 每个矩形算六个 排序后类似最长上升子序
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#define N 40
using namespace std;
struct node
{
int x,y,z;
}rc[N*];
int g,dp[];
void init(int a,int b,int c)
{
rc[++g].x = a;
rc[g].y = b;
rc[g].z = c;
rc[++g].x = b;
rc[g].y = a;
rc[g].z = c;
rc[++g].x = a;
rc[g].y = c;
rc[g].z = b;
rc[++g].x = b;
rc[g].y = c;
rc[g].z = a;
rc[++g].x = c;
rc[g].y = b;
rc[g].z = a;
rc[++g].x = c;
rc[g].y = a;
rc[g].z = b;
}
bool cmp(node a,node b)
{
if(a.x==b.x)
return a.y>b.y;
return a.x>b.x;
}
int main()
{
int i,j,n,a,b,c,kk=;
while(cin>>n)
{
g=;kk++;
if(n==) break;
memset(dp,,sizeof(dp));
for(i = ;i <= n ; i++)
{
scanf("%d%d%d",&a,&b,&c);
init(a,b,c);
}
sort(rc+,rc+g+,cmp);
for(i = ; i <= g ; i++)
dp[i] = rc[i].z;
for(i = ; i <= g ; i++)
for(j = ; j < i ; j++)
{
if(rc[j].x>rc[i].x&&rc[j].y>rc[i].y)
dp[i] = max(dp[i],dp[j]+rc[i].z);
}
int maxz=;
printf("Case %d: maximum height = ",kk);
for(i = ; i <= g ; i++)
maxz = max(dp[i],maxz);
cout<<maxz<<endl;
}
return ;
}
hdu1081http://acm.hdu.edu.cn/showproblem.php?pid=1081 记录从i到j行g列的和 转换为一维的最大子段和
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
int a[][],s[][][],c[][][];
int main()
{
int i,j,k,n,g;
while(scanf("%d",&n)!=EOF)
{
memset(s,,sizeof(s));
memset(c,,sizeof(c));
for(i = ; i <= n ; i++)
for(j = ;j <= n ;j++)
scanf("%d",&a[i][j]);
for(i = ; i <= n ; i++)
for(j = ;j <= n ; j++)
{
s[j][j][i] = a[j][i];
for(g = j+; g <= n ; g++)
s[j][g][i]=a[g][i]+s[j][g-][i];
}
int maxz = -INF,tmaxz=;
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
tmaxz=;
for(g = ;g <= n ;g++)
{
tmaxz+=s[i][j][g];
if(tmaxz>maxz)
maxz=tmaxz;
if(tmaxz<)
tmaxz = ;
}
}
cout<<maxz<<endl; }
return ;
}
hdu1087 水题
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
int a[];
LL dp[];
int main()
{
int i,j,k,n;
while(cin>>n)
{
if(!n) break;
memset(dp,,sizeof(dp));
for(i = ; i <= n ; i++)
{
cin>>a[i];
dp[i] = a[i];
}
for(i = ;i <= n ; i++)
for(j = ; j < i ; j++)
if(a[i]>a[j])
dp[i] = max(dp[i],dp[j]+a[i]);
LL maxz=dp[];
for(i = ;i <= n ;i++)
if(dp[i]>maxz)
maxz = dp[i];
cout<<maxz<<endl;
}
return ;
}
hdu1158http://acm.hdu.edu.cn/showproblem.php?pid=1158二维DP 三重循环 以前居然做过 好扯 居然一点印象没有 好认真的推了半张纸。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
int dp[][],num[];
int main()
{
int i,j,k,n,m,a,b,c,g;
while(cin>>n)
{
if(!n) break;
cin>>a>>b>>c;
memset(dp,,sizeof(dp));
memset(num,,sizeof(num));
int maxz=,minz;
for(i = ; i <= n ;i++)
{
cin>>num[i];
if(num[i]>maxz)
maxz = num[i];
if(num[i]<minz)
minz = num[i];
}
for(i = ;i <= n ;i++)
for(j = ; j <= maxz ; j++)
dp[i][j] = INF;
for(i = ; i <= maxz ; i++)
dp[][i] = i*(a+b);
for(i = ; i <= n ; i++)
for(j = num[i-] ; j <= maxz ; j++)
for(g = num[i] ; g <= maxz ; g++)
{
if(g>j)
dp[i][g] = min(dp[i][g],dp[i-][j]+(g-j)*a+g*b);
else if(g<j)
dp[i][g] = min(dp[i][g],dp[i-][j]+(j-g)*c+g*b);
else
dp[i][g] = min(dp[i][g],dp[i-][j]+g*b);
}
int maxzz = INF;
for(i = num[n] ;i <= maxz ;i++)
if(dp[n][i]<maxzz)
maxzz = dp[n][i];
cout<<maxzz<<endl;
}
return ;
}
hdu1165http://acm.hdu.edu.cn/showproblem.php?pid=1165 这题确实不能算DP 我还傻乎乎的写了一递归 M比较小 直接推就好 了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
#define N 1000010
int n,m;
LL dp[][N+];
int main()
{
int i,j;
for(i = ; i <= N ; i++)
dp[][i] = i+;
dp[][] = ;
dp[][] = ;
dp[][] = ;
for(i = ; i <= N ; i++)
dp[][i] = dp[][]*dp[][i-]+;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m==)
dp[m][n] = dp[][]+n;
else if(m==)
dp[m][n] = dp[][]*n+dp[][];
cout<<dp[m][n]<<endl;
}
return ;
}
hdu1506 http://acm.hdu.edu.cn/status.php 题不错 记录i左边及右边第一个比它小的位置 用来求以它为高的最大面积 求位置的时候 dp一下下吧
注意。。杭电上long long会无限WA。。用——int64
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 100100
__int64 a[N],dp1[N],dp2[N];
__int64 s;
int main()
{
int i,n;
while(cin>>n)
{
if(!n) break;
for(i = ;i <= n ;i++)
scanf("%I64d",&a[i]);
dp1[] = ;
a[] = -;
for(i = ; i <= n ;i++)
{
if(a[i]>a[i-])
dp1[i] = i-;
else
{
int x = i-;
while(x>=&&a[x]>=a[i])
{
x = dp1[x];
}
dp1[i] = x;
}
}
dp2[n] = n+;
a[n+] = -;
for(i = n-; i >= ;i--)
if(a[i]>a[i+])
dp2[i] = i+;
else
{
int x = i+;
while(x<=n&&a[x]>=a[i])
{
x = dp2[x];
}
dp2[i] = x;
}
long long maxz=;
for(i = ;i <= n ; i++)
{
s = (dp2[i]-dp1[i]-)*a[i];
maxz = max(s,maxz);
}
printf("%I64d\n",maxz);
}
return ;
}
hdu1712http://acm.hdu.edu.cn/showproblem.php?pid=1712 简单二维DP
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[][];
int a[][];
int main()
{
int i,j,g,n,m;
while(cin>>n>>m)
{
if(!n&&!m) break;
memset(a,,sizeof(a));
memset(dp,,sizeof(dp));
for(i = ;i <= n ; i++)
for(j = ;j <= m ; j++)
scanf("%d",&a[i][j]);
for(i = ;i <= n ; i++)
for(j = ; j <= m ; j++)
for(g = ; g<= j ; g++)
dp[i][j] = max(dp[i-][g]+a[i][j-g],dp[i][j]);
int maxz = ;
for(i = ; i <= m ;i++)
maxz = max(maxz,dp[n][i]);
cout<<maxz<<endl;
}
return ;
}
hdu2372http://acm.hdu.edu.cn/showproblem.php?pid=2372 又一水DP
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL __int64
LL dp[][];
int a[];
int main()
{
int i,j,g,n,k;
while(cin>>n>>k)
{
if(!n&&!k) break;
memset(dp,,sizeof(dp));
for(i = ;i <= n ; i++)
{
scanf("%d",&a[i]);
dp[i][] = ;
}
for(i = ; i <= n ;i++)
for(j = ;j<=i&&j <= k ; j++)
for(g = ; g < i ; g++)
if(a[i]>a[g])
dp[i][j] += dp[g][j-];
LL maxz=;
for(i = k ; i <= n ; i++)
maxz+=dp[i][k];
cout<<maxz<<endl;
}
return ;
}
hdu4223http://acm.hdu.edu.cn/showproblem.php?pid=4223 这题不能算DP吧 预处理一下
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define LL __int64
#define INF 0xfffffff
int s[];
int a[];
int main()
{
int i,j,k,n,kk=,t;
cin>>t;
while(t--)
{
cin>>n;kk++;
memset(s,,sizeof(s));
for(i = ; i <= n ; i++)
{
scanf("%d",&a[i]);
s[i] = s[i-]+a[i];
}
int minz=INF;
for(i = ; i <= n ; i++)
for(j = ; j < i ; j++)
{
int x = abs(s[i]-s[j]);
minz = min(minz,x);
}
printf("Case %d: ",kk);
cout<<minz<<endl;
}
return ;
}
hdu4159http://acm.hdu.edu.cn/showproblem.php?pid=4159
一直想推概率 结果怎么也推不出来 后来想到可以推可能的种数 因为太大WA了 又去想推概率 还是没退出 最后除了个很大的数 过了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define MM 1000000000000000.0
double dp[][];
int main()
{
int n,s,i,j;
while(cin>>n>>s)
{
memset(dp,,sizeof(dp));
if(s==)
{
printf("0.00000\n");
continue;
}
dp[][s] = ;
dp[][s-] = ;
for(i = ; i <= n ;i++)
for(j = ; j <= s ; j++)
{
dp[i][j] = dp[i-][j]*+dp[i-][j+];
}
double ss=;
for(i = ; i <= s ; i++)
{
ss+=dp[n][i]/MM;
}
dp[n][] = dp[n][]/MM;
double x = -1.0*dp[n][]/ss;
printf("%.5lf\n",x*);
}
return ;
}