欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-25 16:15:59
-Problem Link-emmmmm这里n^3卡过去了,后续会上传新的优化后的打法题目Sample-in2 3 2 1 2 3 2 3 4 1 2Sample-out5思路DP,很容易想到设一个f[t]=t的时间内所能得到的最大金币转移为:f[t]=max(f[t-j]+money-price)代码这个是没卡过的96分,便于放注释就放上来了,卡过100分的请往下拉拉。#include#include#in...

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


题目

【DP】洛谷P1070 道路游戏O(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

相关标签: DP 暴力/模拟