P1052 过河

动态规划的好题

状态转移很简单,dp[i] = dp[i-k] + st[i] ,k是移动距离,st[i]判断i位置是否有石头,但是距离太大,需要压缩路径。

K∈[1,10],lcm[1,10] = 2520,将石子间的距离距离对2520取模。而后进行DP递推即可

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
#define LL long long
#define INF 999999999
const int mod = ; int st[];
int d[];
int pos[];
int dp[]; int main()
{
int L;
int S,T,M;
cin >> L >> S >> T >> M;
for(int i=;i<=M;i++)
cin >> pos[i];
sort(pos+,pos++M);
for(int i=;i<=M;i++)
d[i] = (pos[i] - pos[i-])%;
for(int i=;i<=M;i++)
{
pos[i] = pos[i-] + d[i];
st[pos[i]] = ;
}
int n = pos[M];
for(int i=;i<=n+T;i++)
dp[i] = M;
dp[] = ;
for(int i=;i<=n+T;i++)
{
for(int j=S;j<=T;j++)
{
if(i >= j)
dp[i] = min(dp[i],dp[i-j]);
dp[i] += st[i];
}
}
int ans = M;
for(int i=n;i<=n+T;i++)
ans = min(ans,dp[i]);
cout << ans << endl;
return ;
}
上一篇:网络流24题——试题库问题 luogu 2763


下一篇:Jquery-控制table的奇偶数色列