PKU campus 2018 A Wife——差分约束？/dp

题目：http://poj.openjudge.cn/campus2018/A

有正规的差分约束做法，用到矩阵转置等等。

但也有简单(?)的dp做法。

　　有一个结论(?)：一定要么在一天一点也不选，要么在一天选了7个小时。

　　于是dp[ i ]表示第 i 天选了7个小时、之前合法的方案数。可以从i-1到i-7转移。答案是n到n-6。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int N=1e5+;

int T,n;

ll dp[N],c[N],ans;

int main()

{

  scanf("%d",&T);

  while(T--)

    {

      memset(dp,0x3f,sizeof dp);dp[]=;//

      scanf("%d",&n);ans=0x3f3f3f3f;

      for(int i=;i<=n;i++)scanf("%lld",&c[i]);

      for(int i=;i<=n;i++)

    for(int j=i-;j>=i-&&j>=;j--)//>=0

      dp[i]=min(dp[i],dp[j]+*c[i]);

      for(int i=n;i>=n-&&i>=;i--)ans=min(ans,dp[i]);

      printf("%lld\n",ans);

    }

  return ;

}