首页 > 代码库 > zoj 1483 划分类DP

zoj 1483 划分类DP

2024-07-19 05:36:16   220人阅读

还是看了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


联系
我们