首页 > 代码库 > zoj 1483 划分类DP
zoj 1483 划分类DP
还是看了little_w大神写的才知道怎么写，看完发现自己题意也理解错了，里面有个neighboring，意思就是你指定任务的时候指定的是原序列中连续的一段
然后就是怎么DP了，新学了个很好的dp模型 dp[i][j]表示前i个robot已经分担了j个任务是否可行，可行为1，不可行为0.所以对于某个当前的dp[i][j],只要找到一个合法的dp[i-1][w]存在，即可把当前值也设置为存在。这个模型就可以把当前robot包含了0个 1个 。。。m个都囊括进去了。想通了这个，其他没什么了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing namespace std;int n,m,k;int s[510];int dp[510][510];int main(){ while (scanf("%d%d%d",&n,&m,&k)!=EOF) { for (int i=1;i<=m;i++){ scanf("%d",&s[i]); s[i]+=s[i-1]; } LL L,R; if (s[m]%n==0){ L=s[m]/n-k; R=s[m]/n+k; } else{ L=s[m]/n-k+1; R=s[m]/n+k; } if (L<0) L=0; memset(dp,0,sizeof dp); for (int i=0;i<=m;i++)dp[0][i]=1; for (int i=1;i<=n;i++){ for (int j=0;j<=m;j++){ for (int w=j;s[j]-s[w]<=R && w>=0;w--){ if (s[j]-s[w]<L) continue; if (dp[i-1][w]) dp[i][j]=1; } } } if (dp[n][m]) puts("possible"); else puts("impossible"); } return 0;}
zoj 1483 划分类DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。