define cnblogs sigma set lin clas == problem swe
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1600
题意:
给你一个长度为n的木板,让你把这个木板切割成四段(长度为整数),并且要求这四段可以构成一个四边形。
问你有多少种切割方法(切割点不同就算不同)。
题解:
构成四边形的条件:
任意一边长度 < 周长/2
证明:设四边为a,b,c,d。因为有a < b+c+d,所以2*a < a+b+c+d = C,所以a < C/2。
简化问题:
给你n个小木块,排成一排。问你将这些小木块分成四部分,且能构成四边形的方案数。
表示状态:
dp[i][j] = combinations
i:已经选了前i个木块
j:已经分成了j部分
找出答案:
ans = dp[n][4]
第n块已经选了,共被分成了4部分。
如何转移:
dp[i][j] = ∑ dp[i-k][j-1](k <= i, k < (n+1)/2)
同时保证下标 >= 0,以及边长k < 周长/2。
边界条件:
dp[0][0] = 1
others = 0
什么都没选为一种方案。
优化:
前缀和。
(其实不优化也能过。。。)
AC Code:
- // state expression:
- // dp[i][j] = combinations
- // i: considering ith board
- //
- // find the answer:
- // ans = dp[n][4]
- //
- // transferring:
- // dp[i][j] = sigma dp[i-k][j-1]
- // k: 1 to min(half,i)
- //
- // boundary:
- // dp[0][0] = 1
- // others = 0
- #include <iostream>
- #include <stdio.h>
- #include <string.h>
- #define MAX_N 2505
- using namespace std;
- int n;
- int dp[MAX_N][5];
- int sum[MAX_N][5];
- void read()
- {
- cin>>n;
- }
- int cal_sum(int x,int y,int k)
- {
- if(x==0) return sum[y][k];
- return sum[y][k]-sum[x-1][k];
- }
- void update_sum(int x,int y)
- {
- if(x==0) sum[x][y]=dp[x][y];
- else sum[x][y]=sum[x-1][y]+dp[x][y];
- }
- void solve()
- {
- memset(dp,0,sizeof(dp));
- dp[0][0]=1;
- for(int i=0;i<=n;i++)
- {
- sum[i][0]=1;
- }
- for(int j=1;j<=4;j++)
- {
- for(int i=1;i<=n;i++)
- {
- dp[i][j]=cal_sum(max(0,i-(n+1)/2+1),i-1,j-1);
- update_sum(i,j);
- }
- }
- }
- void print()
- {
- cout<<dp[n][4]<<endl;
- }
- int main()
- {
- read();
- solve();
- print();
- }
BZOJ 1600 [Usaco2008 Oct]建造栅栏:dp【前缀和优化】
来源: http://www.bubuko.com/infodetail-2335618.html