首页 > 代码库 > poj 1036 Gangsters
poj 1036 Gangsters
http://poj.org/problem?id=1036
题意:N个土匪,伸缩门的范围是K, 时间T, 伸缩门在【0, k】范围内变动,每个单位时间可以不变伸长或者缩短一个单位。给出每个最烦到达的时刻,取得的成就,和肥胖程度。即如果伸缩门的长度和土匪的肥胖程度一样,即得到成就。
状态转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j],dp[i-1][j+1])+a[i][j];
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6 7 int dp[2][103]; 8 int t[200],p[200],s[200]; 9 int n,k,t1;10 bool vis[300002];11 int max1(int a,int b,int c)12 {13 return (a>b?a:b)>c?(a>b?a:b):c;14 }15 16 17 int main()18 {19 while(scanf("%d%d%d",&n,&k,&t1)!=EOF)20 {21 memset(vis,false,sizeof(vis));22 for(int i=1; i<=n; i++){23 scanf("%d",&t[i]);24 vis[t[i]]=true;25 }26 for(int i=1; i<=n; i++)27 scanf("%d",&p[i]);28 for(int i=1; i<=n; i++)29 scanf("%d",&s[i]);30 memset(dp,0,sizeof(dp));31 for(int i=0; i<=t1; i++)32 {33 for(int j=1; j<=k+1&&j<=i; j++)34 {35 int sum=0;36 if(vis[i])37 {38 for(int c=1; c<=n; c++)39 {40 if(s[c]==j&&t[c]==i)41 {42 sum+=p[c];43 }44 }45 }46 if(j==1)47 {48 dp[i&1][j]=max(dp[(i-1)&1][j],dp[(i-1)&1][j+1])+sum;49 }50 else if(j==k)51 dp[i&1][j]=max(dp[(i-1)&1][j],dp[(i-1)&1][j-1])+sum;52 else53 dp[i&1][j]=max1(dp[(i-1)&1][j],dp[(i-1)&1][j-1],dp[(i-1)&1][j+1])+sum;54 }55 }56 int ans=0;57 for(int i=1; i<=k+1; i++)58 {59 ans=max(ans,dp[t1&1][i]);60 }61 printf("%d\n",ans);62 }63 return 0;64 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。