题解：单纯形；转化为对偶问题；
对于最大化 cx，满足约束 Ax<=b ，x>0
对偶问题为
最小化 bx，满足约束 ATx>=c ，x>0 （AT为A的转置）
这一题的内存真是坑QwQ;
参考代码为：
1 /************************************************************** 2 Problem: 3112 3 User: SongHL 4 Language: C++ 5 Result: Accepted 6 Time:1800 ms 7 Memory:80004 kb 8 ****************************************************************/ 9 10 #include11 using namespace std;12 #define clr(a,b) memset(a,b,sizeof a)13 #define lowbit(x) x&-x14 #define RI register int15 #define eps 1e-616 typedef long long ll;17 const int INF=0x3f3f3f3f;18 inline int read()19 {20 int x=0,f=1; char ch=getchar();21 while(ch<'0'||ch>'9') { if(ch=='-') f=-1;ch=getchar();}22 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}23 return x*f;24 }25 const int N=1005;26 const int M=10005;27 int n,m;28 double a[N][M],b[M],c[M],v;29 inline void pivot(int l,int e)//矩阵的转秩30 {31 b[l]/=a[l][e];32 for(int j=1;j<=n;++j)33 {34 if(j!=e) a[l][j]/=a[l][e]; 35 }36 a[l][e]=1/a[l][e];37 for(int i=1;i<=m;++i)38 {39 if(i!=l&&fabs(a[i][e])>0)40 {41 b[i]-=a[i][e]*b[l];42 for(int j=1;j<=n;++j)43 {44 if(j!=e) a[i][j]-=a[i][e]*a[l][j];45 }46 a[i][e]=-a[i][e]*a[l][e];47 }48 }49 v+=c[e]*b[l];50 for(int j=1;j<=n;++j)51 {52 if(j!=e) c[j]-=c[e]*a[l][j];53 }54 c[e]=-c[e]*a[l][e];55 }56 57 inline double simplex()58 {59 while(1)60 {61 int e=0,l=0;62 for(e=1;e<=n;++e)63 {64 if(c[e]>eps) break;65 }66 if(e==n+1) return v;67 double mn=INF;68 for(int i=1;i<=m;++i)69 {70 if(a[i][e]>eps&&mn>b[i]/a[i][e]) mn=b[i]/a[i][e],l=i;71 }72 if(mn==INF) return INF;73 pivot(l,e);74 }75 }76 int main()77 {78 n=read(),m=read();79 for(int i=1;i<=n;++i) b[i]=read();80 for(int i=1;i<=m;++i)81 {82 int s,t;83 s=read(),t=read(),c[i]=read();84 for(int j=s;j<=t;++j) a[j][i]=1;//aT85 }86 swap(n,m);87 printf("%d\n",(int)(simplex()+0.5));88 return 0;89 }90 /*91 5 392 1 5 6 3 493 2 3 194 1 5 495 3 5 296 */97