‘壹’ ACM 高手进! 地址http://acm.upc.e.cn/problem.phpcid=1027&pid=2
是一个背包的动态规划题。
dp[i][j]代表前i个中和对m取余是i的最大个数。
总复杂度n*m
应该是可以过的。
‘贰’ 一道动态规划练习题
我也没看出来，你看看这个
#include<iostream>
using namespace std;
int dp[210][10001];
int main()
{
int k;
cin>>k;
while(k--)
{
memset(dp,0,sizeof dp);
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(i&&j)
cin>>dp[i][j];
else dp[i][j]=-1000; //这里要注意考虑边界
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int temp=max(dp[i-1][j],dp[i][j-1]); 如果(1,1)为负那么temp就会为0，这样错误就产生了
for(int l=2;l<=j;l++)
if(j%l==0)
if(dp[i][j/l]>temp)
temp=dp[i][j/l];
if(temp!=-1000)
dp[i][j]+=temp;
}
cout<<dp[n][m]<<endl;
}
}
我是倒着推得 以为 f[i][j]=max{f[i-1][j],f[i][j-1],f[i][j/k]}+data[i][j];
可是怎么也没写出来 而且还不好理解
得出的数还那么大 想不通。。。。。。。。。。。。。。。
后来看旭哥的代码
是从前向后推得 f[i+1][j]=max(f[i][j]+a[i][j-1],f[i+1][j]);
f[i][j+1]=max(f[i][j]+a[i-1][j],f[i][j+1]);
f[i+1][j]是在f[i][j]向下走的
这段代码表示是从前面那个跳过来的 然后跟新这个值
while(1){
int p = j*k;
if (p > m) break;
f[i][p] = max(f[i][p], f[i][j] + a[i-1][p-1]);
++k;
}
#include<stdio.h>
int Max(int x,int y,int z)
{
int m;
m=x;
if(y>m)
m=y;
if(z>m)
m=z;
return m;
}
int main()
{
int t,n,m,i,j,k,max;
int map[22][1002],dp[22][1002];
//freopen("input.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(i=0;i<=n;i++)
dp[i][0]=-1000;
for(j=0;j<=m;j++)
dp[0][j]=-1000;
dp[0][1]=dp[1][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
max=-1000;
for(k=2;j/k>=1;k++)
if(dp[i][j/k]>max && j%k==0)
max=dp[i][j/k];
dp[i][j]=Max(dp[i-1][j],dp[i][j-1],max)+map[i][j];
}
printf("%d\n",dp[n][m]);
}
return 0;
}
‘叁’ 怎么实现php:自动编号规则：日期＋当天项目的编号
怎么实现php:自动编号规则：日期＋当天项目的编号?当天项目编号从0开始，到第二天又是从0开始的。
‘肆’ 求一个动态规划题的c(c++)和matlab代码
matlab的数学语言是最方便的了，如果看它都不能理解，直接看c++就更难了。
可执行代码，math不是已经给了算法function了么。
若你说的是可执行程序，那加一些输入输出接口代码就行了。
----------------------
C++编个矩阵计算都麻烦死了，不然干嘛用matlab语言咧，如果不是舍不得那一点计算时间。
ps:我不懂什么叫泛型算法，呵呵，太专业了。
‘伍’ 求一些简单的动态规划问题
动态规划典型例题(试题+数据+标程):
http://www.coderspace.net/bbs/viewthread.php?tid=414&extra=page%3D1
pascal的一百个基本算法（包含DP）：
http://www.coderspace.net/bbs/viewthread.php?tid=109&extra=page%3D1
其实DP的关键，在于状态设计，既要消除后效性，又不能有冗余维
‘陆’ ACM一题，动态规划题目
#include <stdio.h>
void work(int num)
{
int arr[101][101];
long longarr[101][101];
int by,lx,rx;
long sum,lsum,max=-127;
for(lx=1;lx<=num;lx++)
for(rx=1;rx<=num;rx++)
{
scanf("%d",&arr[lx][rx]);
longarr[lx][rx]=0;
}
for(by=1;by<=num;by++)
{
for(lx=1;lx<=num;lx++)
{
sum=0;
for(rx=lx;rx<=num;rx++)
{
sum=sum+arr[by][rx];
lsum=sum+longarr[lx][rx];
if (lsum>max) max=lsum;
if (lsum<0) lsum=0;
longarr[lx][rx]=lsum;
}
}
}
printf("%d\n",max);
}
int main()
{
int num;
while(scanf("%d",&num)==1)
{
work(num);
}
return 0;
}
#include <stdio.h>
void work(int num)
{
int arr[101][101];
long longarr[101][101];
int by,lx,rx;
long sum,lsum,max=-127;
for(lx=1;lx<=num;lx++)
for(rx=1;rx<=num;rx++)
{
scanf("%d",&arr[lx][rx]);
longarr[lx][rx]=0;
}
for(by=1;by<=num;by++)
{
for(lx=1;lx<=num;lx++)
{
sum=0;
for(rx=lx;rx<=num;rx++)
{
sum=sum+arr[by][rx];
lsum=sum+longarr[lx][rx];
if (lsum>max) max=lsum;
if (lsum<0) lsum=0;
longarr[lx][rx]=lsum;
}
}
}
printf("%d\n",max);
}
int main()
{
int num;
while(scanf("%d",&num)==1)
{
work(num);
}
return 0;
}
‘柒’ http://acm.h.e.cn/showproblem.phppid=1003 求大牛解释
这种经典算法题晚上一大堆，自己搜搜呗，无非就是动态规划和分治法
‘捌’ 一道动态规划的编程题，请用C或C++编程（最好C++）
是图论题吧........
这个可以用Floyd-Warshall 算法
具体可以看http://www.nocow.cn/index.php/Floyd-Warshall%E7%AE%97%E6%B3%95
网上介绍的很多,这个算法就是用DP的
‘玖’ PASCAL动态规划编程问题
官方解法为最短路把每种状态[a1][a2][a3][a4][a5]（a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5）看成一个点，则至多7776个点，而每个优惠就是一条边，则至多105条边。接下来就是求[0,0,0,0,0]到目标状态的最短路，用Dijkstra(Heap优化)即可。
但是我觉得用DP更方便
DP解法你可以参考这里 http://www.nocow.cn/index.php/USACO/shopping
再有问题再说···
‘拾’ 求几道动态规划的例题和C/C++的解法
网络之星2014预选赛第二题：
http://star..com/forum/forum.php?mod=viewthread&tid=3151