835
poj 1157 LITTLE SHOP OF FLOWERS dp
幾個月沒碰過算法，現在完全不會了。
再過幾周就要考試了，抓緊時間恢複一下
這是個簡單dp，之前一直以不會dp為借口躲避這些題目，其實就是太懶了不想想。但是逃避總是逃不過的，於是恢複訓練就從dp開始
注意這題每個花都必須要取到，之前這一點錯了很多次
簡單可以寫出這樣的dp代碼
</pre><pre name="code" >#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int org[105][105];
int dp[105][105];
int main()
{
//freopen("1.txt","r",stdin);
while(~scanf("%d%d",&F,&V))
{
int i,j;
memset(org,0,sizeof(org));
memset(dp,0,sizeof(dp));
for(i=1;i<=F;i++)
for(j=1;j<=V;j++)
{
scanf("%d",&org[i][j]);
}
dp[1][0]=org[1][1];
for(i=1;i<=F;i++){
for(j=i;j<=V;j++){
dp[i][j]=org[i][j]+dp[i-1][j-1];
if(j!=i)dp[i][j]=max(dp[i][j-1],dp[i][j]);
}
}
printf("%d\n",dp[F][V]);
}
}
發現實際上dp數組隻用了兩行，於是循環數組優化
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int org[105][105];
int dp[2][105];
int main()
{
//freopen("1.txt","r",stdin);
while(~scanf("%d%d",&F,&V))
{
int i,j;
memset(org,0,sizeof(org));
memset(dp,0,sizeof(dp));
for(i=1;i<=F;i++)
for(j=1;j<=V;j++)
{
scanf("%d",&org[i][j]);
}
dp[0][0]=org[1][1];
bool flag=0;
for(i=1;i<=F;i++){
for(j=i;j<=V;j++){
dp[flag][j]=org[i][j]+dp[!flag][j-1];
if(j!=i)dp[flag][j]=max(dp[flag][j-1],dp[flag][j]);
}
flag=!flag;
}
printf("%d\n",dp[!flag][V]);
}
}
到此為止?顯然不。兩次循環明顯可以合並
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int dp[2][105];
int main()
{
//freopen("1.txt","r",stdin);
while(~scanf("%d%d",&F,&V))
{
int i,j;
memset(dp,0,sizeof(dp));
bool flag=0;
int t;
for(i=1;i<=F;i++){
for(j=1;j<=V;j++){
scanf("%d",&t);
dp[flag][j]=t+dp[!flag][j-1];
if(j>i)dp[flag][j]=max(dp[flag][j-1],dp[flag][j]);
}
flag=!flag;
}
printf("%d\n",dp[!flag][V]);
}
}
Any More? 當然，因為實際上狀態轉移隻用了兩個數加上一行。但是這時的代碼已經不好理解了
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int dp[105];
int main()
{
//freopen("1.txt","r",stdin);
while(~scanf("%d%d",&F,&V))
{
int i,j,t,last,now;
memset(dp,0,sizeof(dp));
for(i=1;i<=F;i++){
for(j=1;j<=V;j++){
scanf("%d",&t);
now=t+dp[j-1];
if(j>i)now=max(last,now);
dp[j-1]=last;last=now;
}
}
printf("%d\n",now);
}
}
還有嗎？實際上用的真的是兩個數加一行嗎？顯然不是，還可以更加簡化，不多都是常數上的了，而且代碼更加難以理解，就不寫了
最後更新：2017-04-03 05:39:56