【DP】洛谷P1070 道路游戏O(n^3)

-Problem Link-
emmmmm这里n^3卡过去了

---

题目

Sample-in

2 3 2 
1 2 3 
2 3 4 
1 2

Sample-out

5

---

思路

DP，很容易想到设一个f[t]=t的时间内所能得到的最大金币
转移为：f[t]=max(f[t-j]+money-price)

---

代码

这个是没卡过的96分，便于放注释就放上来了，卡过100分的请往下拉拉。

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,p,w,w1,price[1001],money[1001][1001],f[1001];
int main(){
 scanf("%d%d%d",&n,&m,&p);
 for(int i = 1; i <= n; ++i)
   for(int j = 1; j <= m; ++j)
    scanf("%d",&money[i][j]);
 for(int j = 1; j <= m; ++j)   //前缀和处理一下
   for(int i = 1; i <= n; ++i){
    if(i==1) money[i][j] += money[n][j-1];
    else money[i][j] += money[i-1][j-1];
   }
 for(int i = 1; i <= n; ++i)
   scanf("%d",&price[i]);
 for(int t = 1; t <= m; ++t){   //时间轴
  f[t] = -100000000;  //初始化，因为结果可能为负数
     for(int i = 1; i <= n; ++i){  //从这个点买个机器人
      w = i-1; if(w==0) w = n;  //前缀和用
      for(int j = 1; j <= min(p,t); ++j){ //机器人走的步数
        w1 = i+(j%n)-1; if(w1>n) w1-=n; if(w1==0) w1=n;  //最终走到的点
        f[t] = max(f[t], f[t-j]+money[w1][t]-money[w][t-j]-price[i]);  //如上所述
        //之前取到过的+路上的金币+机器人价格
   }
     }
 }
    printf("%d ",f[m]);   //输出
} 

100分的。

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,p,w,w1,k,pt,price[1001],money[1001][1001],f[1001];
int read(){
 int xx=0; char c;
 c = getchar();
 while(c>'9'||c<'0') c = getchar();
 while(c<='9'&&c>='0'){
  xx = xx*10+c-48;
  c = getchar();
 }
 return xx;
}
int main(){
 n=read();
 m=read();
 p=read();
 for(int i = 1; i <= n; ++i)
   for(int j = 1; j <= m; ++j)
    money[i][j]=read();
 for(int j = 1; j <= m; ++j)
   for(int i = 1; i <= n; ++i){
    if(i==1) money[i][j] += money[n][j-1];
    else money[i][j] += money[i-1][j-1];
   }
 for(int i = 1; i <= n; ++i)
   price[i]=read();
 for(int t = 1; t <= m; ++t){
  pt = min(p,t);
  f[t] = -1000000000;
     for(int i = 1; i <= n; ++i){
      w = i-1;
      w = w==0?n:w; 
      for(int j = 1; j <= pt; ++j){
        w1 = (i+j-1)%n;
        w1 = w1==0?n:w1;
        k=f[t-j]+money[w1][t]-money[w][t-j]-price[i];
        f[t] = f[t]<k?k:f[t];
   }
     }
 }
    printf("%d ",f[m]); 
} 

本文地址：https://blog.csdn.net/qq_42937087/article/details/107852188