『壹』 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