本文共 1281 字，大约阅读时间需要 4 分钟。
题目链接
令dp[i][j]为走到目标为i处，手里拿着第j把伞，同时注意，在某处可能存在不止一把伞
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#pragma comment(linker, "/stck:1024000000,1024000000")#define lowbit(x) (x&(-x))#define max(x,y) (x>=y?x:y)#define min(x,y) (x<=y?x:y)#define MAX 100000000000000000#define MOD 1000000007#define pi acos(-1.0)#define ei exp(1)#define PI 3.1415926535897932384626433832#define ios() ios::sync_with_stdio(true)#define INF 0x3f3f3f3f#define mem(a) (memset(a,0,sizeof(a)))typedef long long ll;int dp[2006][2006],a,n,m;int rain[2006],umbre[2006];int val[2006],pos[2006];int main(){ scanf("%d%d%d",&a,&n,&m); memset(rain,0,sizeof(rain)); memset(umbre,0,sizeof(umbre)); a++; for(int i=0,x,y;i i) continue; if(j) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+val[j]); if(!rain[i]) dp[i+1][0]=min(dp[i+1][0],dp[i][j]); if(umbre[i]) dp[i+1][umbre[i]]=min(dp[i+1][umbre[i]],dp[i][j]+val[umbre[i]]);//同一个点可能存在多个雨伞 } } int ans=INF; for(int i=0;i<=m;i++) ans=min(ans,dp[a][i]); printf("%d\n",ans>=INF?-1:ans); return 0;}
转载于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/9151923.html