动态规划集合
动态规划，少说也做了，30 40道了但是感觉还是没有入门，接下来一星期将重新做动态规划，hdu入门的，uva入门的，外加poj的，把动态规划都重新学一下
1.Robberies （hdu2955） （01背包变形）
第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和…
实际上可以将其转化为安全的概率，则两个概率相乘，就是两次抢劫的安全概率了。 正确的方程是:f[j]=max(dp[j],dp[j-v[i]]*(1-p[i])) 其中,dp[j]表示抢j块大洋的最大的逃脱概率,条件是dp[j-v[i]]可达,也就是之前抢劫过; 始化为:dp[0]=1 (抢0块大洋肯定不被抓嘛)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=10010;//100*100
int v[MAXN];
double dp[MAXN],p[MAXN];
int main()
{
int T,i,j,m;
double pi;
scanf("%d",&T);
while(T--)
{
scanf("%lf%d",&pi,&m);
int sum=0;
for(i=1;i<=m;i++)
{
scanf("%d%lf",&v[i],&p[i]);
sum+=v[i];
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1;i<=m;i++)
{
for(j=sum;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]*(1-p[i]));//这里是dp[j]
}
}
for(i=sum;i>=0;i--)//从最大的价值开始递减
{
if(dp[i]>=1-pi)//达到某次价值的概率大于其妈妈给的安全概率，就输出结果
{
printf("%d\n",i);
break;
}
}
}
return 0;
}2.最大报销额（hdu1864）（01背包）
这道题没有什么难点，可是还是wa的我郁闷，很简单，错的地方是一张发票里，A，B，C可以出现多次，所以此次A类的总价格所有A的和，
把A和求出来再去判断是否大于600
至于状态方程，dp[j]=max(dp[j],dp[j-p[i]+p[i])这里的价值和容量是一个
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=3100000;
int dp[MAXN],p[MAXN];
int main()
{
int i,m,j,n,flag;
int ta,tb,tc;
char ch;
double t,limit,sum;
while(scanf("%lf%d",&limit,&n))
{
if(n==0) break;
int lim=limit*100;
for(i=1; i<=n; i++)
{
scanf("%d",&m);
sum=flag=0;
ta=tb=tc=0;
for(j=1; j<=m; j++)
{
getchar();
scanf("%c:%lf",&ch,&t);
if(ch=='A') ta+=t*100;
else if(ch=='B') tb+=t*100;
else if(ch=='C') tc+=t*100;
else flag=1;
if(ta>60000 || tb>60000 || tc>60000) flag=1;
}
sum=ta+tb+tc;
if(flag ||sum>100000)
{
p[i]=0;
continue;
}
p[i]=sum;
}
memset(dp,0,sizeof(dp));
for(i=1; i<=n; i++)
{
for(j=lim; j>=p[i]; j--)
{
dp[j]=max(dp[j],dp[j-p[i]]+p[i]);
}
}
printf("%.2lf\n",1.0*dp[lim]/100);
}
return 0;
}3.最大连续子序列
求集合中连续和最大的子序列，输出和，并输出其子序列的首尾
状态转移方程:dp[i]=max(dp[i-1]+a[i],a[i]);
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=10010;
const int INF=0x7fffffff;
int a[MAXN];
int d[MAXN];
int main()
{
int pos1,pos2;
int n,i,left,MAX,right;
while(scanf("%d",&n) && n)
{
for(i=0; i<n; i++)
scanf("%d",&a[i]);
d[0]=a[0];
MAX=a[0];
left=right=pos1=pos2=0;
for(i=1; i<n; i++)
{
if(a[i]>a[i]+d[i-1])
{
d[i]=a[i];
pos1=pos2=i;
}
else
{
d[i]=a[i]+d[i-1];
pos2=i;
}
if(MAX<d[i])
{
MAX=d[i];
left=pos1,right=pos2;
}
}
if(MAX<0) printf("0 %d %d\n",a[0],a[n-1]);
else printf("%d %d %d\n",MAX,a[left],a[right]);
}
return 0;
}4.Max Sum
同上
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=100100;
const int INF=0x7fffffff;
int a[MAXN];
int d[MAXN];
int main()
{
int pos1,pos2;
int n,i,left,MAX,right;
int cas=1;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("Case %d:\n",cas++);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
d[0]=a[0];
MAX=a[0];
left=right=pos1=pos2=0;
for(i=1; i<n; i++)
{
if(a[i]>a[i]+d[i-1])
{
d[i]=a[i];
pos1=pos2=i;
}
else
{
d[i]=a[i]+d[i-1];
pos2=i;
}
if(MAX<d[i])
{
MAX=d[i];
left=pos1,right=pos2;
}
}
printf("%d %d %d\n",MAX,left+1,right+1);
if(T) printf("\n");
}
return 0;
}5.Largest Rectangle in a Histogram(hdu1506)
给出N个连续的方块组，求出最大矩形面积
对于某一块方块，找出它能向左向右延伸的长度，延伸的方法就是找出若左边界的方块大于它，则它的左边界就变为左边那块方块的左边界，对于右同理
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=101000;
int a[MAXN];
int l[MAXN],r[MAXN];
int main()
{
int n,i,t;
__int64 MAX,sum;//结果超出
while(scanf("%d",&n)!=EOF && n)
{
a[0]=a[n+1]=-1;//对于0的边界十分重要，如果左边界是0，则左边就是-1了，越界了
MAX=0;
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
r[i]=l[i]=i;
}
for(i=1; i<=n; i++)//核心
{
while(a[l[i]-1]>=a[i])
{
l[i]=l[l[i]-1];
}
}
for(i=n; i>=1; i--)
{
while(a[r[i]+1]>=a[i])
{
r[i]=r[r[i]+1];
}
sum=(__int64)a[i]*(r[i]-l[i]+1);
if(sum>MAX) MAX=sum;
}
printf("%I64d\n",MAX);
}
return 0;
}1506的加强版/
先从上到下进行长度的累加，然后从左到右进行dp
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1010;
char a[MAXN][MAXN];
int l[MAXN][MAXN],r[MAXN][MAXN];
int d[MAXN][MAXN];
int main()
{
int T,i,j,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(d,-1,sizeof(d));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%s",&a[i][j]);
r[i][j]=l[i][j]=j;
}
}
for(i=1;i<=m;i++)
{
if(a[1][i]=='F') d[1][i]=1;
else d[1][i]=0;
for(j=2;j<=n;j++)
{
if(a[j][i]=='F') d[j][i]=d[j-1][i]+1;
else d[j][i]=0;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
while(d[i][l[i][j]-1]>=d[i][j])
{
l[i][j]=l[i][l[i][j]-1];
}
}
for(j=m;j>=1;j--)
{
while(d[i][r[i][j]+1]>=d[i][j])
{
r[i][j]=r[i][r[i][j]+1];
}
}
}
__int64 MAX=0,sum;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
sum=3*d[i][j]*(r[i][j]-l[i][j]+1);
if(MAX<sum) MAX=sum;
}
}
printf("%I64d\n",MAX);
}
return 0;
}7.Bone Collector（hdu2602）（01背包）
简单的背包问题，但是还是wa的郁闷，memset忘记了。。。原先只是把dp[0]=0，后面的都没有清零
若后面的值没有清零，很容易影响到下次推倒的时间记录上次的结果，导致max出现错误
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1100;
int dp[MAXN];
int w[MAXN],p[MAXN];
int main()
{
int T,i,j,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&p[i]);
for(i=1;i<=n;i++) scanf("%d",&w[i]);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=m;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
}
}
printf("%d\n",dp[m]);
}
return 0;
}8.Super Jumping! Jumping! Jumping!(hdu1087)
最大递增和 状态转移方程dp[i]=max(sum[i])+a[i]
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1100;
int a[MAXN];
int f[MAXN];
int main()
{
int i,j,n,m,MAX;
while(scanf("%d",&n) && n)
{
for(i=1;i<=n;i++) scanf("%d",&a[i]);
f[1]=a[1];
for(i=2;i<=n;i++)
{
MAX=a[i];
for(j=1;j<=i-1;j++)
{
if(a[i]>a[j])
{
int t=f[j]+a[i];
if(t>MAX) MAX=t;//找出最大的f[j]
}
}
f[i]=MAX;
}
MAX=0;
for(i=1;i<=n;i++) if(f[i]>MAX) MAX=f[i];
printf("%d\n",MAX);
}
return 0;
}9.命运(hdu2571)
数组从左上角到右下角选一条路径使幸运数最大，
刚开始一直wa，究其原因是，我忽略了，对于f数组来说有可能其的值是负的，所以一开始将MAX赋予0，这是致命的。。。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN=1100;
int a[MAXN][MAXN];
int f[MAXN][MAXN];
int main()
{
int i,j,n,m,MAX,T,k;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
}
}
f[1][1]=a[1][1];
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
int MAX=0;
if(i==1) MAX=f[i][j-1];
else if(j==1) MAX=f[i-1][j];
else MAX=max(f[i-1][j],f[i][j-1]);
for(int t=1; t<j; t++)
{
if(j%t==0)
{
if(MAX<f[i][t]) MAX=f[i][t];
}
}//以上过程是选出最大的前一阶段是哪条
f[i][j]=a[i][j]+MAX;
}
}
printf("%d\n",f[n][m]);
}
return 0;
}叠加立方体，叠上的立方体宽长必须分别小于下面立方体的长宽
分析：最长递增子序列，f[j]=max(f[j])+a[i]
这道题错的地方就是排序的时候要面积排序，判断的时候要两次判断xi和xj，yi和yj比较，xi和yj，xj和yi比较
对于别人的代码他们先前输入三个数字的时候已经排序了，所以放置的时候已经保证了，xi必定小于yi了
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=200;
int f[MAXN];
struct Node
{
int x,y,z;
}node[MAXN];
bool cmp(Node a,Node b)
{
return a.x*a.y>b.x*b.y;
}
int main()
{
int n,i,j,MAX;
int cas=1;
while(scanf("%d",&n) &&n )
{
for(i=0;i<n;i++)
{
scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].z);
//这里排序了，后面就不需要两次判断了
node[i+n].x=node[i].y,node[i+n].y=node[i].z,node[i+n].z=node[i].x;
node[i+2*n].x=node[i].x,node[i+2*n].y=node[i].z,node[i+2*n].z=node[i].y;
node[i+3*n].x=node[i].y,node[i+3*n].y=node[i].x,node[i+3*n].z=node[i].z;
}
sort(node,node+4*n,cmp);
int cnt=0;
int ans=0;
f[0]=node[0].z;
for(i=1;i<n*4;i++)
{
int MAX=0;
for(j=0;j<i;j++)
{
if((node[j].x>node[i].x && node[j].y>node[i].y) || (node[j].x>node[i].y && node[j].y>node[i].x))
{
if(f[j]>MAX) MAX=f[j];
}
}
f[i]=MAX+node[i].z;
if(ans<f[i]) ans=f[i];
}
printf("Case %d: maximum height = %d\n",cas++,ans);
}
return 0;
}将所有物品平等分，多重背包，背包容量上线时总和除以2
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=120000;
int n,limit,val[MAXN],num[MAXN],V;
int f[MAXN];
void ZeroOnePack(int cost,int worth)
{
for(int v=V;v>=cost;v--)
{
f[v]=max(f[v],f[v-cost]+worth);
}
}
void CompletePack(int cost,int worth)
{
for(int v=cost;v<=V;v++)
{
f[v]=max(f[v],f[v-cost]+worth);
}
}
void MultiplePack(int cost,int worth,int num)
{
if(cost*num>=V)
CompletePack(cost,worth);
else
{
int k=1;
while(k<num)
{
ZeroOnePack(k*cost,k*worth);
num-=k;
k*=2;
}
ZeroOnePack(num*cost,num*worth);
}
}
int main()
{
int i;
while(scanf("%d",&n))
{
if(n<0) break;
limit=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&val[i],&num[i]);
limit+=val[i]*num[i];
}
V=limit/2;
memset(f,0,sizeof(f));
for(i=0;i<n;i++)
MultiplePack(val[i],val[i],num[i]);
int a=max(f[V],limit-f[V]);
int b=min(f[V],limit-f[V]);
printf("%d %d\n",a,b);
}
return 0;
}12.数塔(hdu2084)
题意：求塔顶到塔底总和的最大路径，状态转移方程f[i][j]=max(f[i+1][j],f[i+1][j+1])+v[i][j];
#include<stdio.h>
#include<string.h>
const int MAXN=110;
int a[MAXN][MAXN];
int main()
{
int T,n,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=n;i>=2;i--)
{
for(j=1;j<=i-1;j++)
{
if(a[i][j]>a[i][j+1])
{
a[i-1][j]+=a[i][j];
}
else a[i-1][j]+=a[i][j+1];
}
}
printf("%d\n",a[1][1]);
}
return 0;
}13.免费馅饼（hdu1176）
题意：从位置5开始，每次可以随意朝两边走一格，在不同的时间里，天上会掉下馅饼，问能够得到最大的馅饼数量是多少
数塔的升级版，f[i][j]=max(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+v[i][j]
考虑边界的问题，由于边界是两个的比较
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=100010;
int f[MAXN][15];
int main()
{
int n,i,j;
int a,b;
while(scanf("%d",&n) && n)
{
memset(f,0,sizeof(f));
int src=0;
for(i=1; i<=n; i++)
{
scanf("%d%d",&a,&b);
f[b][a]++;
if(src<b) src=b;
}
int MAX;
for(i=src-1;i>=0;i--)
{
f[i][0]+=max(f[i+1][0],f[i+1][1]);
for(j=1;j<=9;j++)
{
MAX=max(f[i+1][j],max(f[i+1][j-1],f[i+1][j+1]));
f[i][j]+=MAX;
}
f[i][10]+=max(f[i+1][9],f[i+1][10]);
}
printf("%d\n",f[0][5]);
}
return 0;
}14.I NEED A OFFER!（hdu1203）
题意:申请学校要花钱，每所学校申请的价钱不一样，总共有n元，有m所学校能够申请，每所学校申请成功的概率是p
求问最少申请上一所学校的概率是多少，我们只要求出每所学校没有申请到的概率p1，1-p1就是申请到的最少一所学校
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=10010;
int val[MAXN];
double p[MAXN];
double dp[MAXN];
int main()
{
int n,m,i,j;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
for(i=1;i<=m;i++)
{
scanf("%d%lf",&val[i],&p[i]);
}
memset(dp,0,sizeof(dp));
for(i=1;i<=m;i++)
{
for(j=n;j>=val[i];j--)
{
dp[j]=max(dp[j],1-(1-dp[j-val[i]])*(1-p[i]));//j-val[i]这里忘记了
}
}
printf("%.1lf%%\n",dp[n]*100);
}
return 0;
}15.FATE（hdu2159）
题意：二维完全背包，有两个限制条件
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=110;
int val[MAXN];
int w[MAXN];
int dp[MAXN][MAXN];
int main()
{
int n,m,k,s,i,j,t;
while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
{
for(i=1; i<=k; i++)
scanf("%d%d",&val[i],&w[i]);
memset(dp,0,sizeof(dp));
for(i=1; i<=k; i++)
{
for(j=1; j<=s; j++)//第一个限制条件，杀怪的数量
{
for(t=w[i]; t<=m; t++)//第二个限制条件，消耗的忍耐度
{
dp[j][t]=max(dp[j][t],dp[j-1][t-w[i]]+val[i]);
}
}
}
int flag=0;
for(j=0; j<=m; j++)
{
if(dp[s][j]>=n)
{
flag=1;
break;
}
}
if(flag) printf("%d\n",m-j);
else
{
printf("-1\n");
}
}
return 0;
}16.How to Type（hdu2577）
题意：摁最少的键位输入一窜字符窜（包含大小写切换shift+capslk）
分析：定义两个数组dp_close,dp_open分别表示当前状态大写关着和开着
当字母是大写字母的时候
dp_open[i]=min(dp_open[i-1]+1,dp_close[i-1]+2);开着的时候自然直接输入字母，若开关是关着的,先打开开关，再输入字母 dp_close[i]=min(dp_open[i-1]+2,dp_close[i-1]+2);开着的时候先输入字母再关上，若关着恩shift+字母
当是小写字母的时候
dp_open[i]=min(dp_open[i-1]+2,dp_close[i-1]+2);开着的时候shift+字母，若关着先打开在输入字母 dp_close[i]=min(dp_open[i-1]+2,dp_close[i-1]+1);开着的时候先关上再输入字母，若关着直接输入
这个表示由上一状态输入字母+变为当前要求状态共需多少步
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=110;
char str[MAXN];
int dp_open[MAXN],dp_close[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dp_open,0,sizeof(dp_open));
memset(dp_close,0,sizeof(dp_close));
scanf("%s",str);
if(str[0]>='A' && str[0]<='Z') dp_open[0]=2,dp_close[0]=2;
else dp_close[0]=1,dp_open[0]=2;
for(int i=1;str[i];i++)
{
if(str[i]>='A' && str[i]<='Z')
{
dp_open[i]=min(dp_open[i-1]+1,dp_close[i-1]+2);
dp_close[i]=min(dp_open[i-1]+2,dp_close[i-1]+2);
}
else
{
dp_open[i]=min(dp_open[i-1]+2,dp_close[i-1]+2);
dp_close[i]=min(dp_open[i-1]+2,dp_close[i-1]+1);
}
}
int len=strlen(str);
printf("%d\n",min(dp_open[len-1]+1,dp_close[len-1]));
}
return 0;
}17.Coins（hdu2844）
题意：给出硬币面值及数量，求解其所能凑成的不超过m的硬币类型有多少个
多重背包，价值和花费都是其本身
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=100100;
int val[MAXN],num[MAXN];
int f[MAXN];
int n,m;
int ans;
void ZeroOnePack(int cost,int worth)
{
for(int v=m;v>=cost;v--)
{
f[v]=max(f[v],f[v-cost]+worth);
}
}
void CompletePack(int cost,int worth)
{
for(int v=cost;v<=m;v++)
{
f[v]=max(f[v],f[v-cost]+worth);
}
}
void MultiplePack(int cost,int worth,int num)
{
if(cost*num>=m)
CompletePack(cost,worth);
else
{
int k=1;
while(k<num)
{
ZeroOnePack(k*cost,k*worth);
num-=k;
k*=2;
}
ZeroOnePack(num*cost,num*worth);
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
ans=0;
memset(f,0,sizeof(f));
for(i=1; i<=n; i++)scanf("%d",&val[i]);
for(i=1; i<=n; i++)scanf("%d",&num[i]);
for(i=1;i<=n;i++)
MultiplePack(val[i],val[i],num[i]);
for(i=1;i<=m;i++) if(f[i]==i) ans++;//对于i容量他的价值是i的话，说明i可达
printf("%d\n",ans);
}
return 0;
}18.Beans（hdu2845）
题意：求最大和，如果取了某一个格子的数字，则该格子的上一行下一行，前一列后一列都不可以在取了
分析：先算行的最大和再算列的最大和，dp[i]=max(dp[i-2]+a[i],dp[i-1])
这里要和最大递增子序列要区分开
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=200020;
int a[MAXN],f[MAXN];
int n,m;
int main()
{
int i,j,k;
int res,ans,MAX;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&a[j]);
}
MAX=a[1];
for(j=2; j<=m; j++)
{
a[j]=max(a[j-2]+a[j],a[j-1]);
}
f[i]=a[m];
}
MAX=f[1];
for(i=2; i<=n; i++)
{
f[i]=max(f[i-1],f[i-2]+f[i]);
}
printf("%d\n",f[n]);
}
return 0;
}19.Largest Submatrix（hdu2870）
题意：最大子矩阵，其中相同矩阵式a,b,c三种，wxy是可以变的
暴力依次枚举a，b，c+dp 和1505思想类似
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1100;
int n,m;
char str[MAXN][MAXN];
int f[MAXN][MAXN];
int l[MAXN][MAXN],r[MAXN][MAXN];
int ans;
void DP()
{
int i,j;
int MAX=0,sum;
for(i=1; i<=n; i++)
{
f[i][0]=f[i][m+1]=-1;
for(j=1; j<=m; j++) r[i][j]=l[i][j]=j;
for(j=1; j<=m; j++)
while(f[i][l[i][j]-1]>=f[i][j])
{
l[i][j]=l[i][l[i][j]-1];
}
for(j=m; j>=1; j--)
while(f[i][r[i][j]+1]>=f[i][j])
{
r[i][j]=r[i][r[i][j]+1];
}
for(j=1; j<=m; j++)
{
sum=(r[i][j]-l[i][j]+1)*f[i][j];
if(MAX<sum) MAX=sum;
}
if(ans<MAX) ans=MAX;
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
for(i=1; i<=n; i++)
{
scanf("%s",str[i]+1);
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if(str[i][j]=='a' || str[i][j]=='w' || str[i][j]=='y' || str[i][j]=='z') f[i][j]=f[i-1][j]+1;
else f[i][j]=0;
}
DP();
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if(str[i][j]=='b' || str[i][j]=='w' || str[i][j]=='x' || str[i][j]=='z') f[i][j]=f[i-1][j]+1;
else f[i][j]=0;
}
DP();
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if(str[i][j]=='c' || str[i][j]=='x' || str[i][j]=='y' || str[i][j]=='z') f[i][j]=f[i-1][j]+1;
else f[i][j]=0;
}
DP();
printf("%d\n",ans);
}
return 0;
}20.Matrix Swapping II（hdu2830）
题意：最大子矩阵，其中列可以任意交换
分析：枚举所有的行，然后记录到这一行为止该列的最大连续1的个数
然后对于每一行枚举的连续列都从大到小排序一次，则最大矩阵就是max（a[i]*i）
例如1001 则其变换连续1个数就是 1001
1101 2102
0101 0203
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1100;
int dp[MAXN],b[MAXN][MAXN];
char a[MAXN][MAXN];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n,m,i,j;
int ans;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
for(i=1; i<=n; i++)
{
scanf("%s",a[i]+1);
for(j=1; j<=m; j++)
{
if(a[i][j]=='1') b[i][j]=b[i-1][j]+1;
else b[i][j]=0;
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
dp[j]=b[i][j];
sort(dp+1,dp+m+1,cmp);
for(j=1; j<=m; j++) if(ans<dp[j]*j) ans=dp[j]*j;
}
printf("%d\n",ans);
}
return 0;
}23.搬寝室
题意：给定n个物品，搬走k*2个物品，选取的物品使其疲劳度最低（疲劳度为左右手的差的平方）。
dp[i][j]表示i物品的选j对的疲劳度
对于第i个物品，比较当前物品放与不放的大小，选取小的，则dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])^2,dp[i-1][j])
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x7fffffff;
const int MAXN=2010;
int dp[MAXN][MAXN],a[MAXN];
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int n,k,i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=0;
sort(a+1,a+n+1,cmp);
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
{
for(j=1;j<=k;j++)
{
dp[i][j]=INF;
}
}
dp[0][0]=0;
for(i=2;i<=n;i++)//物品
{
for(j=1;j*2<=i;j++)//找的对数
{
dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);
}
}
printf("%d\n",dp[n][k]);
}
return 0;
}对于物品i，若i=j*2,说明物品的个数刚好够匹对的个数，则所有的物品必须都放进去
那么dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])^2
若i>j*2，则比较放与不放i个物品的大小，取小的
dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])^2,dp[i-1][j])
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=2010;
int dp[MAXN][MAXN],a[MAXN];
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int n,k,i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
memset(dp,0,sizeof(dp));
dp[0][0]=0;
for(j=1;j<=k;j++)//第几对,这里是j
{
for(i=2*j;i<=n;i++)//物品，这里是i
{//若当前物品刚好够匹对物品的数量，则所有物品要放进去，所以该dp[i][j]就是前一个
//dp直接加上当前的就可以了
if(i==j*2) dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);
//否则就比较前一个加上当前物品大还是，不加上该物品的大，类似01背包思想
else dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);
}
}
printf("%d\n",dp[n][k]);
}
return 0;
}26.How many ways（hdu1978）
29.Max Sum Plus Plus（滚动数组+DP）好题在做
这道题确实不错，既能够了解滚动数组，又能加深对于dp的理解
题意：n个数进行m个组合，使m个组合的和最大。
状态转移方程dp[i][j]=max(dp[i][j-1],max{dp[i-1][j-1]})+a[j]
dp[i][j-1]认为的是a[j]附属于i段，从而表示段数不变多加了一个数
dp[i-1][j-1]则表示a[j]独立成为了一段，所以就得找出i-1段的时候物品数十多少的时候dp最大
View Code题意：找出w从小到大排序，s从大到小排序的一组序列，输出最大序列数和数列位置
分析：按照体重从小到大排序，然后找最大递减子序列，用index数组记录每一项接在哪一项后面，回溯输出
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1100;
struct Node
{
int w,s,pos;
}node[MAXN];
int d[MAXN];
int index[MAXN];
bool cmp(Node a,Node b)
{
if(a.w==b.w) return a.s>b.s;
return a.w<b.w;
}
void Print(int pos)
{
if(d[pos]==1) {printf("%d\n",node[pos].pos); return ;}
else
{
Print(index[pos]);
printf("%d\n",node[pos].pos);
}
}
int main()
{
int i,j;
int cas=1,MAX=0,pos=1;
while(scanf("%d%d",&node[cas].w,&node[cas].s)!=EOF)
{
node[cas].pos=cas;
cas++;
}
memset(d,0,sizeof(d));
node[cas].pos=cas;
sort(node+1,node+cas,cmp);
for(i=1;i<=cas;i++)
{
d[i]=1;
for(j=1;j<i;j++)
{
if(node[i].w>node[j].w && node[i].s<node[j].s && d[j]+1>d[i])
{
d[i]=d[j]+1;
index[i]=j;
}
}
if(MAX<d[i]) MAX=d[i],pos=i;
}
printf("%d\n",MAX);
Print(pos);
return 0;
}32
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=110;
int dp[MAXN][MAXN],a[MAXN][MAXN];
int row[]= {-1,1,0,0};
int col[]= {0,0,1,-1};
int ans;
int n,m;
bool ok(int x,int y)
{
if(x>=0 && y>=0 && x<n && y<n) return true;
return false;
}
int DFS(int x,int y)
{
int i,j;
if(dp[x][y]) return dp[x][y];
dp[x][y]=a[x][y];
for(i=0; i<4; i++)
{
int xx=x;
int yy=y;
for(j=1; j<=m; j++)//持续i的步数走k步
{
xx=xx+row[i];
yy=yy+col[i];
if(ok(xx,yy) && a[x][y]<a[xx][yy])
{
dp[x][y]=max(dp[x][y],DFS(xx,yy)+a[x][y]);
}
}
}
if(ans<dp[x][y])
{
ans=dp[x][y];
}
return dp[x][y];
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m))
{
if(n==-1 && m==-1) break;
ans=0;
memset(dp,0,sizeof(dp));
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
scanf("%d",&a[i][j]);
}
}
DFS(0,0);
printf("%d\n",ans);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-02-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读